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

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

شبیه سازی حرارتی 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

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

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