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

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

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

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

نوروز را به همه ی مردم شاد باش می گویم!