این یک نمونه ساده از رفتار جمعی و گروهی[۳۳] است که افراد برای رسیدن به یک هدف نهایی همکاری میکنند. این روش کاراتر از زمانی است که افراد جداگانه کنش کنند. Swarm را میتوان به صورت مجموعهای سازمان یافته از عاملها[۳۴] یا موجوداتی تعریف کرد که با یکدیگر همکاری میکنند. در کاربردهای محاسباتی هوش ازدحامییا گروهی[۳۵] از موجودات یا عاملهایی مانند مورچهها، زنبورها، موریانهها، ماهیها، پرندگان، و یا حتی چکههای آب در رودخانه الگو برداری میشود. در این نوع اجتماعات هر یک از موجودات یا عاملها ساختار نستباً سادهای دارند ولی رفتار گروهی آنها پیچیده به نظر میرسد. برای نمونه، در کولونی مورچهها، هر یک از مورچهها یک کار سادهی ویژهای را انجام میدهد ولی به طور گروهی، کردار و رفتار مورچهها؛ ساختن لانه، نگهبانی از ملکه و نوزادان، پاکداری لانه، یافتن بهترین منابع خوراکی و بهینهسازی راهبرد جنگی را تضمین میکند. رفتار کلی یک Swarm به گونهی غیر خطی از همآمیختگی رفتارهای تک تک اجتماع بدست میآید. یا به زبانی دیگر، یک رابطهی بسیار پیچیده میان رفتار گروهی و رفتار فردی یک اجتماع وجود دارد. رفتار گروهی، تنها وابسته به رفتار فردی عاملها و افراد اجتماع نیست بلکه به چگونگی همکنشی[۳۶] و تعامل میان افراد نیز وابسته است. همکنشی بین افراد، تجربهی افراد دربارهی پیرامون[۳۷] را افزایش میدهد و مایه پیشرفت اجتماع میشود. ساختار اجتماعی Swarm بین افراد مجموعه کانالهای ارتباطی ایجاد میکند که طی آن افراد میتوانند به داد و ستد تجربههای شخصی بپردازند. مدلسازی محاسباتی Swarmها کاربردهای امیدبخش و بسیاری را به ویژه در زمینه بهینه سازی[۳۸] در پی داشته است. الگوریتهای فزایندهای از بررسی Swarmهای گوناگون پیشنهاد شدهاند. از این رده، میتوان به کولونی مورچهها[۳۹] و دستهی پرندگان[۴۰] اشاره نمود. با اینکه دانش هوش جمعی[۴۱]، دانشی نو میباشد؛ هم اکنون، کاربردهای رو به گسترشی از آن شناخته شده است. با این رشد روزافزون، هوش جمعی میتواند نقش ارزندهای را در دانشهای گوناگون بر دوش بگیرد.
الگوریتم کلونی مورچهها[۴۲]
روش بهینهسازی گروه مورچهها یکی از زیر شاخههای هوش گروهی است که در آن از رفتار مورچههای واقعی برای یافتن کوناهترین گذرگاه میان لانه و چشمه خوراکی[۴۳] الگوبرداری شده است. هر مورچه برای یافتن خوراک در گرداگرد لانه به گونه تصادفی حرکت و در طی راه با بهره گیری از ماده شیمیایی به نام فرومن، از خود ردی بر جای میگذارد. هر چه شمار مورچههای گذر کرده از یک گذرگاه بیشتر باشد، میزان فرومن انباشته روی آن گذرگاه نیز افزایش مییابد. مورچههای دیگر نیز برای گزینش گذرگاه، به میزان فرومن آن مینگرند و به احتمال زیاد گذرگاهی را که دارای بیشترین فرومن است بر میگزینند. به این شیوه، حلقه بازخور مثبت پدید میآید. گذرگاه هرچه کوتاهتر باشد، زمان رفت و برگشت کاهش و مورچه بیشتری در یک زمان مشخص از آن میگذرد. از این رو، انباشت فرومن آن افزایش مییابد. شایان یادآوری است که گزینش گذرگاه دارای بیشترین فرومن، قطعی نیست و احتمالی است. به همین سبب، امکان یافتن بهترین جواب[۴۴] وجود دارد. روش ACO، نوعی فرااکتشافی است که برای یافتن گشایشهای تقریبی برای مسائل بهینهسازی آمیختاری[۴۵] سودمند است.
شکل۲‑۲ – روال حرکت مورچه در ACO [41]
روش ACO، مورچههای ساختگی بهوسیلهی حرکت بر روی گرافِ مساله و با وانهادن[۴۶] نشانههایی بر روی گراف، همچون مورچههای واقعی که در گذرگاه خود نشانههای به جا میگذارند، سبب میشوند که مورچههای ساختگی بعدی بتوانند گشایشهای بهتری را برای مساله فراهم نمایند. [۲۱]
PSO یا بهینه سازی گروهی ذرات
روش بهینهسازی ازدحام ذرات[۴۷] یک الگوریتم جستجوی اجتماعی است که از روی رفتار اجتماعی دستهه ای پرندگان مدل شده است. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شکل بهینهی دسته به کار گرفته شد. در PSO، ذرات[۴۸] در فضای جستجو جاری میشوند. تغییر مکان ذرات در فضای جستجو تحت تأثیر تجربه و دانایی خودشان و همسایگانشان است. بنابراین موقعیت دیگر ذرات[۴۹] Swarm روی چگونگی جستجوی یک ذرات اثر میگذارد. نتیجهی مدلسازی این رفتار اجتماعی فرایند جستجویی است که ذرات به سمت نواحی موفق میل میکنند. ذرات در Swarm از یکدیگر میآموزند و بر مبنای دانایی بدست آمده به سمت بهترین همسایگان خود میروند. اساس کار PSO بر این اصل استوار است که در هر لحظه هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته است و بهترین مکانی که در کل همسایگیاش وجود دارد، تنظیم میکند. فرض کنید میخواهیم زوج مرتب (x,y) را طوری بدست آوریم که تابع ،F(x,y)=2x+y، مینیمم شود. ابتدا نقاطی را به صورت تصادفی در فضای جستجو، روی صفحهی x-y انتخاب میکنیم. فرض کنید این Swarm را به ۳ همسایگی تقسیم کنیم که در هر همسایگی نقاط موجود با یکدیگر تعامل دارند. در هر همسایگی هر یک از نقاط به سمت بهترین نقطه در آن همسایگی و بهترین مکانی که آن نقطه تاکنون در آن قرار داشته است، حرکت میکند. برای حل یک مسئله چند متغیر بهینهسازی میتوان از چند Swarm استفاده کرد که هر یک از Swarmها کار مخصوصی را انجام میدهند. این همان ایدهای است که کلونی مورچه از آن ریشه میگیرد. روش PSO یک الگوریتم روش جستجوی سراسری [۵۰] است که با بهرهگیری از آن میتوان با مسائلی که پاسخ آنها یک نقطه یا سطح در فضای n بعدی میباشد، برخورد نمود. در اینچنین فضایی، فرضیاتی مطرح میشود و یک سرعت ابتدایی به آنها اختصاص داده میشود، همچنین کانالهای ارتباطی بین ذرات درنظر گرفته میشود. سپس این ذرات در فضای پاسخ حرکت میکنند، و نتایج حاصله بر مبنای یک «ملاک شایستگی» پس از هر بازهی زمانی محاسبه میشود. با گذشت زمان، ذرهها به سمت ذرههایی که دارای سنجه شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند، شتاب میگیرند. مزیت اصلی این روش بر راهبردهای بهینهسازی دیگر، این است که شمار فراوان ذرات ازدحام کننده، سبب نرمش پذیری و انعطاف روش در برابر مشکل پاسخ بهینه محلی [۵۱] میگردد.[۲۲, ۲۳]
ایده PSO، برای اولین بار توسط کندی و ابرهارت در سال ۱۹۹۵ مطرح شد. PSO، یک الگوریتم محاسبه ای تکاملی الهام گرفته از طبیعت و براساس تکرار میباشد. منبع الهام این الگوریتم، رفتار اجتماعی حیوانات، همانند حرکت دسته جمعی پرندگان و ماهیها بود. از این جهت که PSO نیز با یک ماتریس جمعیت تصادفی اولیه، شروع میشود، شبیه بسیاری دیگر از الگوریتمهای تکاملی همچون الگوریتم ژنتیک پیوسته و الگوریتم رقابت استعماری است. برخلاف الگوریتم ژنتیک ، PSO هیچ عملگر تکاملی همانند جهش و تزویج ندارد. از این جهت میشود گفت که الگوریتم رقابت استعماری شباهت بیشتری به PSO دارد تا به GA.[52] هر عنصر جمعیت، یک ذره نامیده میشود (که همان معادل کروموزوم در GA و یا کشور در الگوریتم رقابت استعماری) است. در واقع الگوریتم PSO از تعداد مشخصی از ذرات تشکیل میشود که به طور تصادفی، مقدار اولیه می گیرند. برای هر ذره دو مقدار وضعیت و سرعت، تعریف میشود که به ترتیب با یک بردار مکان و یک بردار سرعت، مدل میشوند. این ذرات، بصورت تکرارشونده ای در فضای nـبعدی مسئله حرکت میکنند تا با محاسبه مقدار بهینه بودن به عنوان یک ملاک سنجش، گزینههای ممکن جدید را جستجو کنند. بُعد فضای مسئله، برابر تعداد پارامترهای موجود در تابع مورد نظر برای بهینه سازی می باشد. یک حافظه به ذخیره بهترین موقعیت هر ذره در گذشته و یک حافظه به ذخیره بهترین موقعیت پیش آمده در میان همه ذرات، اختصاص مییابد. با تجربه حاصل از این حافظهها, ذرات تصمیم می گیرند که در نوبت بعدی، چگونه حرکت کنند. در هر بار تکرار، همه ذرات در فضای nـبعدی مسئله حرکت میکنند تا بالاخره نقطه بهینه عام، پیدا شود. ذرات، سرعتهایشان و موقعیتشان را بر حسب بهترین جوابهای مطلق و محلی بهروز میکنند. یعنی:
رابطه ۲-۱
رابطه ۲-۲
که در آن :
-
- اعداد تصادفی مستقل با توزیع یکنواخت: ,
میباشند. الگوریتم PSO، بردار سرعت هر ذره را بهروز کرده و سپس مقدار سرعت جدید را به موقعیت و یا مقدار ذره میافزاید. بهروز کردنهای سرعت، تحت تأثیر هر دو مقدار بهترین جواب محلی و بهترین جواب مطلق قرار میگیرند. بهترین جواب محلی و بهترین جواب مطلق، بهترین جوابهایی هستند که تا لحظهی جاری اجرای الگوریتم، به ترتیب توسط یک ذره و در کل جمعیت به دست آمدهاند. ثابتهای , به ترتیب، پارامتر ادراکی و پارامتر اجتماعی نامیده میشوند. مزیت اصلی PSO این است که پیادهسازی این الگوریتم ساده بوده و نیاز به تعیین پارامترهای کمی دارد. همچنین PSO قادر به بهینهسازی توابع هزینهی پیچیده با تعداد زیاد مینیمم محلی است.
شکل ۰۲‑۳ به روز رسانی بردار سرعت و مکان در PSO [42]
در زیر شبه کد مربوط به الگوریتم PSO آورده شده است:
For each particle
Initialize particle
END
Do
For each particle
Calculate fitness value
If the fitness value is better than the best fitness value (pBest) in history
set current value as the new pBest
End
Choose the particle with the best fitness value of all the particles as the gBest
For each particle
Calculate particle velocity according equation (a)
Update particle position according equation (b)
End
v[] = v[] + c1 * rand() * (pbest[] – present[]) + c2 * rand() * (gbest[] – present[]) (a)
present[] = resent[] + v[] (b)
سیستمهای توزیعشده
سیستم عامل توزیع شده در یک محیط شبکهای اجراء میشود. در این سیستم قسمتهای مختلف برنامه کاربر بدون آنکه خود او متوجه شود میتوانند همزمان در چند کامپیوتر مجزا اجراء شده و سپس نتایج نهایی به کامپیوتر اصلی کاربر بازگردند.
کاربران نباید از این موضوع باخبر شوند که برنامه آنها در کجا اجرا میشود و یا فایلهای آنها در کجای شبکه قرار دارد و همه این کارها باید توسط سیستم عامل به صورت خودکار انجام گیرد. به عبارتی دیگر سیستم باید از دید کاربر شفاف باشد و هرچیز را با نام آن فراخوانی کند و کاری به آدرس آن نداشته باشد.
یکی از مزایای مهم سیستمهای توزیع شده سرعت بالای اجرای برنامههاست چرا که یک برنامه همزمان میتواند از چندین کامپیوتر استفاده کند. همچنین به علت توزیع شدن اطلاعات، بانکهای اطلاعاتی حجیم میتوانند روی تعدادی کامپیوترهای شبکه شده قرار بگیرند. لازم نیست که همه اطلاعات به یک کامپیوتر مرکزی فرستاده شود (که در نتیجه این نقل و انتقالات حجیم زمان زیادی به تلف میشود.)
به علت تأخیرهای انتقال در شبکه و نویزهای احتمالی در خطوط انتقالی، قابلیت اطمینان اجرای یک برنامه در یک سیستم بیشتر از قابلیت اطمینان آن در یک سیستم توزیع شده است. همچنین درسیستم توزیع شده اگر یکی از کامپیوترهایی که وظیفه اصلی برنامه جاری را برعهده دارد خراب شود کل عمل سیستم مختل خواهد شد. از طرف دیگر اگر اطلاعاتی همزمان در چند کامپیوتر به صورت یکسان ذخیره گردد ویکی از کامپیوترها خراب شود، دادهها را میتوان از کامپیوترهای دیگر بازیابی کرد از این نظر امنیت[۵۳] افزایش مییابد.
به سیستمهای توزیعشده گاهی سیستمهای ارتباط ضعیف[۵۴] نیز میگویند، چرا که هر پردازنده فرکانس و حافظه مستقلی دارد و پردازندهها از طریق خطوط مخابراتی مختلفی مثل گذرگاههای سریع یا خطوط تلفن ارتباط دارند.
هر سیستمیکه بر روی مجموعهای از ماشینها که دارای حافظه اشتراکی نیستند، اجرا شده و برای کاربران به گونه ای اجرا شود که گویا بر روی یک کامپیوتر میباشند، یک سیستم توزیع شده است. در یک سیستم توزیع شده: یک نرم افزار یا مجموعه نرم افزاری واحد بر روی هر گره اجرا میشود. همه ماشینها یک هستهی[۵۵] مشابه را اجرا میکند. هر هسته منابع خود را کنترل میکند. مواردی که در طراحی سیستم توزیع شده باید در نظر گرفت: شفافیت، قابلیت اطمینان، کارایی خوب، قابلیت گسترش.
قابلیت اطمینان: در دسترس بودن یک فاکتور مهم مرتبط با این سیستمها است. طراحی نباید به گونهای باشد که نیاز به اجرای همزمان مولفههای[۵۶] اساسی باشد. افزونگی بیشتر دادهها باعث افزایش در دسترس بودن شده اما ناسازگاری را بیشتر میکند. قدرت تحمل نقص[۵۷] باعث پوشاندن خطاهای ایجاد شده توسط کاربر میشود.
موضوعات: بدون موضوع
[ 05:00:00 ق.ظ ]