چمران-الكترو كامپ

وبلاگ جدید چمران الکتروکامپ

6 – الگوریتم اجتماع مورچه (Ant Colony Algorithm)

 6-1- معرفی

یکی از مسائلی که به­وسیله­ی زیست­شنا­سان مورد مطالعه قرار گرفته است درك این موضوع است که چگونه موجودات تقریبا کور مانند مورچه­ها کوتاه­ترین مسیر را از لانه­ی خود تا منبع غذا و بر عکس پیدا می­کنند.آن­ها پی بردند که یک رسانه براي ابلاغ اطلاعات بین تک­تک مورچه­ها مورد استفاده قرار می­گیرد و براي تصمیم­گیري درمورد این­که کدام مسیر را انتخاب کنند به­کار می­رود که آن رسانه عبارت است از بو(اثر) ماده­اي به­نام فرومون[1].

 الگوریتم­های لانه­ی مورچه از جمله روش­های فرامکاشفه­ای هستند که برای حل مسایل بهینه­سازی سخت پیشنهاد شده­اند. این الگوریتم­ها در آغاز از رفتارهای اجتماعی پشت سرهم قرار گرفتن و تعقیب کردن الهام گرفته شد، که در جامعه­ی مورچگان مشاهده گردید. یک اجتماع از عامل­های[2] ساده (مورچه­ها) به طور غیر مستقیم از طریق تغییرات پویای (دینامیکی) محیط ارتباط برقرار می­کنند (رد پاهایی از فرومون) و بنابراین بر اساس تجربه­ی اجتماعی آن­ها، یک راه­حل برای یک مسئله ارائه می­دهند.

نخستین الگوریتم از این نوع (سامانه­ی مورچه) برای مسئله­ی فروشنده­ی دوره­گرد طراحی شد،  اما نتایجش چندان امیدبخش نبود.  

6-2- ویژگی­های الگوریتم

این الگوریتم داراي ویژگی­هاي زیر است:

·         چند منظوره است، به عبارت دیگر می­تواند براي انواع مشابه یک مسئله به­کار رود.

·         قوي است، یعنی با کمترین تغییرات براي دیگر مسائل بهینه­سازي ترکیبی به کار برده می­شود.

·         روشی مبتنی بر جمعیت است.

6-3- رفتار طبیعی مورچه

یک مورچه در حال حرکت مقداري فرومون دراندازه­هاي گوناگون از خود بر روي زمین باقی می­گذارد و بدین ترتیب مسیر را به­وسیله­ی بوي این ماده مشخص می­سازد. هنگامی که یک مورچه به­طور تصادفی  و تنها حرکت می­کند با روبه­رو شدن با مسیري که توسط مورچه یا مورچه­هاي قبلی انتخاب شده و داراي بوي فرومون است به احتمال زیاد آن را  انتخاب می­کند و با فرومونی که خود بر جاي می­گذارد بوي آن را در مسیر مذکور تقویت می­نماید.

وقتی رفتار جمعی پدید می­آید، گونه­ای از رفتار خود تقویتی است، یعنی هرچه مورچه ها بو(اثر) ماده­ی مذکور را دنبال کنند آن بو براي مورچه­هاي پیرو آنها جذاب­تر خواهد بود. فرایند گفته شده به وسیله­ی یک حلقه توصیف می­شود، یعنی احتمال این­که یک مورچه یک مسیر را انتخاب کند متناسب باتعداد مورچه­ها­یی که قبلا آن مسیر را انتخاب کرده­اند افزایش می­یابد.

ایده این است که اگر در یک نقطه معین یک مورچه مجبور است از بین مسیرهاي مختلف یکی را انتخاب کند­، مسیرهایی را که توسط مورچه­هاي قبلی بیش­تر انتخاب شده­اند، به عبارت دیگر سطح بوی آن­ها بالاتر است، با احتمال بیش­تري انتخاب خواهد کرد. به­علاوه سطح فرمون بالاتر معادل مسیر­هاي کوتاه­تر خواهد بود.

بدین ترتیب کوتاه­ترین مسیر توسط مورچه­ها انتخاب می­شود. الگوریتم­هایی که ارائه خواهد شد از اجتماع مورچه­ی واقعی سر­چشمه گرفته­اند. سامانه­ی مورچه­ی ارائه شده با استفاده از اجتماع مورچه­ی مصنوعی چند تفاوت عمده با نوع طبیعی آن خواهد داشت:

1. مورچه­هاي مصنوعی مقداري حافظه خواهند داشت،

2. آن­ها کاملا کور نیستند،

3. آن­ها در محیطی زندگی می­کنند که زمان گسسته است.

6-4- سامانه­ی مورچه[3]

در اين بخش سامانه­ی مورچه معرفي می­شود و از مسئله­ی فروشنده­ی دوره­گرد به­عنوان معيار استفاده مي­­گردد. در مسئـله­ی فروشنده­ی دوره­گرد، يك فروشنده سفر خود را از يك شهر آغاز می­کند و پس از يك سفر كامل دوباره به شهر خودش باز مي­گردد و از هر شـهر فـقط يك­بار عبور مي­كند و در ضمن بايد از همه­ی شهرها عبور كند. هدف يافتن كوتاه­ترين مسير براي اين سفر است.

هر مورچه يك نماينده­ی ساده باويژگي­هاي زير است:

1.        يك شهر را براي رفتن انتخاب مي­كند كه تابعي از فاصله­­ی شهر و مقداربوی (اثر) موجود در آن مسير است.

2.        براي واداركردن مورچه­ها جهت انجام سفرهاي منطقي، سفر به شهرهايي كه يك­بار از آن­ها عبوركرده است ممنوع می­شود.

3.     هنگامي كه يك مورچه يك سفركامل انجام مي­دهد مقداري فرمون برروي هرمسير  و  بر جای مي­گذارد.

در ضمن در طبیعت هر چه از مدت زمان گذاشته شدن فرومون بگذرد بو و اثر آن کمتر می­گردد، دلیل آن هم تبخیر این ماده است، پس در الگوریتم زمان نیز موجب کاهش اولویت برخی مسیرها و افزایش اولویت مسیرهای دیگر نسبت به آن­ها می­گردد.

برای این­که شرط تکراری نبودن شهرها و نیز گذشتن از همه­ی آن­ها برقرار گردد، به هر مورچه یک لیست ممنوع نسبت داده می­شود که دارای شهرهای عبور کرده می­باشد.

6-5- بیان الگوریتم

با توجه به تعاريف بخش پیش الگوريتم­ها معرفي مي­شوند. در زمـان صفر يعني مرحله شروع، مورچه­ها درشـهرهاي مختـلف مستقر مي­شوند و ارزش اوليه­ی شدت بو(اثر) بر روي مسيرها تعیین می­گردد. شهر آغازين به عنوان اولين عنصر وارد ليست مي­شود. سپس هرمورچه از شهر  با تابع احتمال   به سمت شهر  حرکت می­کند، كه خود تابعي از دو معيار مطلوبيت است: يكي احتمال اين­كه در گذشته چه تعداد مورچه از مسير رفته­اند، ديگري قابليت رويت[4] كه مي­گويد شهرهاي نزديك براي مورچه­ها مطلوب­تراند.

بعد از  تكرار همه­ی مورچه­ها يك سفر كامل انجام داده­ا­ند وليست ممنوع آ­ن­ها پرشده ا­ست. همچنين كوتـاهترين مسير يافته­شـده به­وسيله­ی مورچه­ها ذخيره شده و ليست­هاي ممنوع خالي مي­شوند. اين فرايند تا زماني كه تعداد سيكل­ها به حداكثر خود برسد يا همه مورچه­ها يك سفر يك­سان انجام دهند ادامه مي­يابد. اين حالت رارفتار ركودي مي­نامند زيرا الگوريتم جستجوي راه­حل­هاي ديگر را متوقف مي­كند.

قابل ذکر است که سه نوع الگوریتم مورچه وجود دارد: 1. چگالی مورچه[5]، 2. تعداد مورچه[6]، 3. دور مورچه[7].

در دو الگوريتم اول مقدار فرمون در پايان هر تكرار تعديل مي­شود. اما در الگوريتم سوم پس از پايان يك دور اين عمل انجام مي­گيرد. پس از انجا­م شدن چند دور فقط به مورچه­اي كه بهترين مسير را مي­پيمايد اجازه ترشح­كردن فرمون داده مي­شود، اين عمـل به منظور جـهت­دار كردن جستجو انجام مي­گيرد يعني با اين كار مورچه­ها در همسايگي بهترين مسـيري كه تاكـنون پیدا شـده است بـه جستـجو مـي­پردازند. دو الگوريتم اول دقيقا مثل هم هستند و فقط از لحاظ تعديل­كردن (به­روزرسانی) فرومون با هم  متفاوت­اند  .

6-6- حالت کلی الگوریتم

الگوریتم اجتماع مورچگان دارای سه بخش اصلی زیر است:

1.        بخش مقداردهی اولیه، که عبارت است از تشکیل گرافی که بر اساس مسئله­ی بهینه­سازی ترکیبی در دست بررسی و پارامترها، با توجه به ارزش­های اولیه­اشان، ساخته می­شود،

2.        بخش ایجاد راه­حل، که در آن هر مورچه راه­حل خودش را برای مسئله تولید می­کند، و تا زمانی که همه­ی مورچه­ها راه­حل خود را کامل کنند ادامه می­یابد،

3.        بخش به­روزرسانی فرومون، که طی آن دنباله­ی فرومون متناظر با هر اتصال در گراف ساختمان بر اساس قانون به روز رسانی، به روز خواهد شد.

6-7- مقایسه با دیگر روش­های فرامکاشفه­ای

الگوریتم کلونی مورچه دارای ویژگی­هایی در مقایسه با دیگر روش­های فرامکاشفه­ای است:

1.        محاسبات گسسته در طبیعت،

2.        فرایند تجزیه­ی واکنش توسط یکی از محصولات خودش[8]،

3.        استفاده از جستجوی حریصانه و اطلاعات اکتشافی سازنده (آگاهانه).

[1] Pheromones

[2] agent

[3] Ant System

[4] Visibility

[5] Ant Density

[6] Ant Quantity

[7] Ant Cycle

[8] Autocatalytic

وبلاگ جدید چمران الکتروکامپ

 جستجوی تابو (Tabu Search)

 تاریخچه

جستجوی تابو نخستین بار توسط فرد گلوور[1] در مقاله­ی منتشر شده در سال 1986]گلوور،1986[ بیان شد، البته این مقاله از بسیاری نظریه­های پیشنهادی در گذشته طی دهه­ی 60 استفاده کرده بود. دو مقاله­ای ]گلوور،1989،گلوور،1990[ که عنوان آنها جستجوی تابو بود بسیاری از اصولی را که امروزه شناخته شده­اند، بیان کردند. برخی از این اصول اقبال چندانی را برای مدت طولانی در میان جامعه­ی علمی به­دست نیاورد. در واقع، در نیمه­ی نخست دهه­ی 90، بیشتر کارهای تحقیقاتی در زمینه­ی جستجوی تابو، دامنه­ی کوچکی از اصول این روش[2] را به کار می­گرفت؛ که عموما محدود به یک لیست تابو[3]  و یک شرط تکاملی[4] ساده بود.

وبلاگ جدید چمران الکتروکامپ

شبیه سازی حرارتی Simulated Annealing

تاریخچه

ساختارهای پیچیده­ی فضای پیکر­بندی[1] مربوط به مسایل بهینه­سازی سخت، شباهت­هایی را با پدیده­های فیزیکی تداعی می­کند، که همین امر سه محقق – اس.کرک پاتریک، سی.دی. گلات و ام.پی. وکی[2]- از انجمن  IBM را به ارائه­ی روش تکرارشونده­ی جدیدی در سال 1982و انتشار آن در سال 1983 سوق داد: یعنی همان شبیه­سازی حرارتی [کرک پاتریک و دیگران، 1983]، که می­تواند از بهینگی (کمینگی) محلی[3] خارج شود. کار مشابهی به طور جداگانه و در همان زمان توسط وی.کرنی[4]  انجام شد که در سال 1985 منتشر گشت.

از همان آغاز پیدایش، شبیه­سازی حرارتی کارایی خود را در زمینه­های گوناگونی همچون طراحی مدارهای الکترونیکی، پردازش تصویر، جمع­آوری زباله­های خانگی، و ... ثابت کرده است. در عوض آشکار شد که این روش برای حل مسایل بهینه­سازی ترکیبی خاصی بیش از حد حریصانه و یا در واقع ناتوان است که این مسایل با روش­های اکتشافی ویژه­ای بهتر حل می­شوند.

[1] Configuration space

[2] S.Kirkpatrick, C.D. Gelatt and M.P. Vecchi

[3] Local minima

[4] V. Cerny

وبلاگ جدید چمران الکتروکامپ

از ژنتیک تا مهندسی

تکامل زیستی چنان موجودات پیچیده و مختاری را تولید کرده است که می­توانند مسایل سخت و شگفت­آوری را حل کنند، از جمله سازگاری مداوم با محیط­های پیچیده، مبهم و همواره در حال دگرگونی. به همین خاطر، موجودات ممتاز، هم­چون پستانداران، از توانایی­های شگفت­آوری در الگوشناسی[1]، یادگیری و هوش برخوردار هستند. دامنه­ی گسترده­ی وضعیت­هایی که زندگی با آن­ها سازگار است نشان می­دهد که فرایند تکامل قدرتمند است و هم­چنین می­تواند دسته­های بسیاری از مسایل را حل کند. این امر به کسی که جهان زنده را مشاهده می­کند اجازه­ی تصور این موضوع را می­دهد که برای ساخت سامانه­های پیچیده و کارامد به گونه­ای رضایت­بخش، به غیر از ایجاد فرایندهای دقیق، که به تدریج از دانش کیفی مربوط به قوانین طبیعت به­دست آمده­اند،  راه­های دیگری نیز وجود دارد.

بر اساس نظریه­ی سی. داروین[2] [داروین، 1859]، سازوکار اصلی تکامل موجودات زنده بر پایه­ی رقابتی است که سازگازترین افراد به محیطشان را انتخاب می­کند در حالی که هنگام انتقال ویژگی­های مفید به فرزندان که موجب بقای والدین می­شود، یک نژاد تضمین می­گردد.  این سازوکار وراثت، به ویژه، بر پایه­ی گونه­ای از همکاری است که با تکثیر جنسی انجام می­گردد.

فرضی که نظریه­ی داروین برای سازوکار تکامل به شمار آورد، که با دانش کنونی ژنتیک نیز غنی شده است، هنوز تایید نشده است. هیچ کس تا امروز تایید نکرده است که این ساز­و­کارها به طور کامل شناخته شده­اند و دیگر هیچ پدیده­ی مهم دیگری پنهان نمانده است. از این­رو مثلا لازم بود که مدت زمان زیادی  بگذرد تا بفهمیم که پرندگان چگونه پرواز می­کنند، که دلیل آن چندان به خاطر برخورد باد با بال­هایشان نبود، که دلیلی قابل مشاهده و گمراه کننده را ایجاد می­کند، بلکه دلیل آن شکل بال­های آن­ها بود، که پدیده­ی مطلوب ایرودینامیک[3] را موجب می­شود.

با  این­حال، نئو- داروینیسم[4] تنها نظریه­ی تکاملی است که تاکنون هرگز نقض نشده است. توسعه­ی ماشین­حساب­های الکترونیکی مطالعه­ی این نظریه را در شبیه­سازی آسان کرد و برخی پژوهش­گران، خیلی پیش­تر در دهه­ی 1950، علاقه­مند به آزمودن آن بر روی مسایل مهندسی بودند. اما این کار چندان راضی­کننده نبود و دلیل آن هم دانش ناکافی از ژنتیک طبیعی در آن زمان و نیز کارایی ضعیف ماشین­حساب­های موجود بود. به­علاوه، آهستگی بسیار زیاد تکامل این تفکر را که چنین فرایندی بتواند به خوبی مورد استفاده قرار گیرد، فلج کرد.

طی دهه­های 1960 و 1970، که ماشین­حساب­های با قدرت معتبر پا به عرصه­ی وجود نهادند، تلاش­های بسیاری برای مدل­سازی فرایند تکامل صورت گرفت. در میان آن­ها، سه زمینه به­طور مستقل پدیدار شد، که تا آغاز دهه­ی 1990، از دید یک­دیگر پنهان بودند:

·         استراتژی­های تکـامل[5] (EA) از اچ. پی. شوفل[6]  و آی. ریچنبرگ[7] [ریچنبرگ، 1965، بیر، 2001] که در میـانه­ی دهه­ی 1960 هم­چون یـک روش بهینه­سازی برای مسایلی که از پارامترهای پیوسته­ی مختلفی استفاده می­کنند، طراحی شد؛

·         برنامه­نویسی تکاملی[8] (EP) از ال. جی، فوگل[9] و دیگران [فوگل و دیگران، 1966] که توانست، در میانه­ی دهه­ی 1960، ساختار ماشین­های با حالات محدود[10] را به وسیله­ی انتخاب­ها و جهش[11] های مکرر گسترش دهد؛ که این امر برای آغاز دورانی در زمینه­ی دیگری از هوش­ مصنوعی مطلوب بود.

·         الگوریتم ژنتیک[12](GA) که در 1975 توسط جی. اچ. هالند[13] [هالند، 1992] ارائه شد، با هدف درک ساز­و­کار موجود در زیر­سامانه­های خود-سازگار[14] ارایه شد.

از آن پس، بر اساس مسایل مختلفی که یابندگان این روش­ها و شاگردانشان با آن­ها برخورد داشتند، این روش­ها دست­خوش تغییرات بسیاری شدند.

[1] Patern Recognization

[2] C. Darwin

[3] Aerodynamic

[4] Neo-Darwinism

[5] Evolution Strategies

[6] H. P. Schwefel

[7] I. Rechenberg

[8] Evolutionary programming

[9] L. J. Fogel

[10] Finite-state Automata

[11] mutation

[12] Genetic Algorithm

[13] J. H. Holland

[14] Self-adaptive

وبلاگ جدید چمران الکتروکامپ

سلام

دراین پست یک ترجمه از کتاب " Metaheuristics for hard optimization" گذاشتم که در مورد الگوریتم کلونی مورچه هاست.اگر چه کوتاه است اما فکر کنم یک معرفی کلی بر این الگوریتم باشه.

در ضمن این متن رو خودم ترجمه کردم پس ممکن است مشکلاتی در واژه پردازی آن باشد.

برای دیدن متن به دنباله نوشته بروید.