تکامل یعنی اینکه انسانها از نسل میمون ها هستند. این ابتدائی ترین و خام ترین برداشتی است که ممکن است شخصی از تکامل داشته باشد و متاسفانه تنها اطلاعی که بسیاری از
افراد از تکامل دارند همین است، که یک آدمی به نام داروین پیدا شده است و ثابت کرده است انسانها قبلاً میمون بوده اند.
در بیان تاریخچه مختصری از تکامل باید گفت که داروین نخستین کسی نیست که تکامل را کشف کرد، هزاران سال پیشاز داروین تئوری تکامل در افسانه ها و اسطوره های برخی از ملت ها وجود داشته است، مثلا هندو ها معتقد بوده اند حیات از آب شروع شده است و اولین موجودات ابتدا در آب شکل گرفتند و بعد به سایر موجودات تبدیل شدند. بعدها دانشمندان و فلاسفه ای مثل تالس تکامل را بصورت فرضیه های طبیعی برای توضیح علمی حیات مطرح کردند اما بررسی علمی و دقیق تکامل در دوران اخیر شکل گرفته است. پیشاز داروین چند دانشمند دیگر مانند لامارک شخصی که زیست شناسی را به معنی امروزی اش بنا نهاد نیز در مورد تکامل مطالعاتی داشتند و نظریاتی را نیز ارائه داده بودند. تفاوت اصلی میان نظریه تکامل لامارک با نظریه داروین در این بود که داروین تکامل را امری گروهی و مربوط به گونه های جانوری میداند ولی لامارک آنرا امری انفرادی میدانسته است، اما با این وجود، این داروین است که پدر تکامل خوانده میشود زیرا درک مدرن ما از تکامل به تئوری گزینش طبیعی بر میگردد که چارلز داروین و آلفرد راسل والاس آنرا در سال ١٨۵٨ در کتاب "مشاء انواع یا ریشه مطرح کردند. (Origin of species) " گونه ها
تعریف گزینش طبیعی:
بر اساس نظریه گزینش طبیعی، طبیعت موجوداتی که ویژگیهای مساعد برای نجات یافتن و ادامه حیات و تکثیر شدن را دارند را حفظ میکند و موجوداتی که این ویژگی ها و صفات را نداشته باشند تدریجا منقرضمیشوند.
گزینش طبیعی در قیاس با گزینش مصنوعی نامگذاری شده است که در آن انسانها گونه خاصی از جانداران را که مورد نظر آنها است انتخاب میکنند و آنها را تکثیر میکنند، مثلا کشاورزان گندم را گزینش کرده و به تکثیر آن کمک میکنند و یا دامداران گاو را گزیده و با پرورشدادن آن به ادامه حیات و تکثیر آن یاری میرسانند، داروین معتقد بود طبیعت نیز چنین میکند، و موجوداتی که بتوانند خود را با شرایط زیستی همساز کنند احتمال ادامه یافتن حیاتشان از باقی جانداران بیشتر خواهد شد و برعکس، یعنی طبیعت نیز بصورت استعاره ای همچون آن کشاورز که گزینش مصنوعی میکند، موجوداتی را انتخاب میکند و باعث گسترشآنها میشود. مفهوم گزینش طبیعی همان تولید مثل افراقی است، یعنی بعضی از اعضای یک گونه بیش از سایر اعضا تولید مثل میکنند و در نتیجه میزان بیشتری از ژن آنها به نسل بعدی انتقال می یابد. گزینش طبیعی از مرکزی ترین یا شاید هم مرکزی ترین نکاتی است که بیولوژی امروزه بر روی آن تمرکز دارد.
تعریف تکامل:
تکامل در بیولوژی، به پروسه ای اطلاق میشود که بر اساس آن، جمعیت گونه ها با ویژگیهای برتر وراثتی افزایشمی یابند و از نسلی به نسل بعدی منتقل میشوند. در طول زمان این ویژگیها به گونه جانوری کمک میکنند که به تعداد بیشتری نسبت به گونه های رقیب تکثیر بیابند و در جمعیت بر آنها تسلط بیابند. اتفاق افتادن این پروسه در مدت های طولانی میتواند پدید آمدن موجودات جدید را توضیح دهد.
بر اساس تئوری تکامل موجودات جدید تر همگی اجداد مشترکی دارند، و برای نشان دادن این شراکت استفاده میشود، بعنوان مثال (Phylogenetic tree) در اجداد، معمولا از درختواره های فیلوژنتیکی ارتباط حیوانات با گیاهان و سایر موجودات را نشان میدهد.
گاه بصورت تصادفی و بر اثر برخی علت های دیگر گاهی اوقات این اطلاعات ژنتیکی بواسطه یک جهش ژنتیکی تغییر پیدا میکنند. اگر جهش ژنتیکی وجود نداشته باشد تمامی موجودات دقیقاً شبیه یکدیگر خواهند بود. این تغییرات ژنتیکی یکی از عوامل تکامل هستند و عامل دیگر نیز شرایط زیستی در محیطی است که این جانداران در آن زندگی میکنند. تغییرات زیست محیطی باعث میشوند موجوداتی که سازگارتر با محیط هستند نجات پیدا کنند و موجوداتی که سازگاری با محیط ندارند نابود شوند.
تکامل هنوز تنها یک نظریه است:
این اعتراض از رایج ترین اعتراضاتی است که عوام نسبت به تکامل مطرح میکنند. این افراد نمیدانند که در دنیای علم هیچ مفهومی بالاتر از تئوری نمیرود و تئوری بالاترین مرحله ایست که یک نظر علمی
میتواند داشته باشد. بسیاری از سایر مفاهیم علمی همچون جاذبه نیوتون، سرعت نور، بیگ بنگ و غیره تماما تئوری هستند، اساساً هرچیز که بر مشاهده مبتنی باشد نمیتواند از مرحله تئوری بالاتر
است، مفاهیمی وجود دارند که Science رود. در برخی از شاخه های علم منظور از علم همان گفته (Theorem) مشتق شده از اصول قطعی ریاضیات هستند به آن دسته از مفاهیم قضیه یا تئورم میشود مثلا روابط فیثاغورس و تالسدو نمونه از قضایا هستند، سایر چیز ها نمیتوانند چیزی جز تئوری باشند. پیرامون این مسئله در نوشتاری با فرنام علم چیست؟ توضیحات بیشتری آورده شده است.
نتیجه آنکه تئوری بودن تکامل نمیتواند از ارزشو درستی آن بکاهد و کسانی که این ایراد را وارد میکنند مفهوم کلمه "تئوری" را در فلسفه علم درک نمیکنند. از این گذشته هر تئوری برای توضیح یک واقعیت
شکل میگیرد، مثلاً تئوری جاذبه نیوتون برای توضیح واقعیت جاذبه شکل گرفته است، دقیقاً همین ارتباط میان تئوری تکامل و خود تکامل بعنوان یک واقعیت وجود دارد.
تکامل تصادفی است و احتمال آن پایین است، پس محال است:
در پاسخ به این شبهه باید گفت نخست اینکه تکامل تماماً مبتنی بر تصادف نیست، شخصی که این اعتراض را مطرح میکند عامل دوم تکامل را که عاملی غیر تصادفی است را نادیده میگیرد، از این گذشته تئوری تکامل تماماً مبتنی بر تصادف نیست، بلکه عوامل جبری نیز در آن نقش بازی میکنند.
بسیاری از بیولوژیست ها معتقدند دو عامل اساسی در تکامل نقش بازی میکنند،
.١
تغییراتی که بر اساس تحولات تصادفی ژنتیکی (جهش ژنتیکی) انجام میگیرند.
.٢
تغییراتی که قدرت و احتمال نجات یافتن و تکثیر موجود را بالا میبرند، که عدم تحقق این تغییرات موجب حذف آن موجود توسط گزینشطبیعی میشود.
کسانی که این اعتراض را بیان میکنند درکی بسیار ضعیف از تئوری احتمالات دارند، اینکه احتمال وقوع یک اتفاق پایین باشد هرگز و هرگز به این معنی نیست که آن اتفاق محال است، لذا این اعتراض نیز از
پایه غلط است. در این مورد در نوشتاری با فرنام "مگر میشود همه چیز بطور تصادفی بوجود آمده باشد؟" توضیحات کافی داده شده است.
AI به دو مکتب فکری تقسیم می شود:
AI قراردادی (Coventional AI) : توسط رسمی سازی (formalism)، تحلیل آماری، تعاریف و اثبات مشخص می گردد (مثل یادگیری ماشین و سیستم های خبره).
هوش محاسباتی: با ویژگی های غیررسمی، غیراحتمالی و اغلب با رویکردهای آزمون و خطا شناخته می شود. هوش محاسباتی به سه بخش اصلی تقسیم می گردد:
شبکه های عصبی
سیستم های فازی
محاسبه تکاملی
الگوریتم های تکاملی تکنیک پیاده سازی مکانیزم هایی مانند تولید مجدد، جهش، ترکیب مجدد(ادغام)، انتخاب طبیعی (فرایندی که توسط آن افرادی دارای مشخصه های مطلوب با احتمال بیشتری برای تولید افراد بعدی به کار می روند. پس مشخصه های مطلوب در نسل بعد عمومی تر می شوند) و بقای شایسته ترین است. ولی محاسبات تکاملی دارای مشخصه های زیر می باشند:
پیشروی، رشد یا توسعه تکراری
مبنی بر جمعیت
جستجوی تصادفی هدایت شده
پردازش موازی
ملهم از زیست شناسی
محاسبات تکاملی اغلب شامل الگوریتم های بهینه سازی فرااکتشافی است مانند:
الگوریتم های تکاملی (شامل الگوریتم ژنتیک، برنامه نویسی تکاملی، استراتژی تکاملی، برنامه نویسی ژنتیک و سیستم های طبقه بندی کننده یادگیر (
هوش گروهی (شامل بهینه سازی گروه مورچگان و بهینه سازی گروه ذرات)
و تا حد کمتری شامل:
خودسازماندهی (نقشه های خودسازمانده ، گاز عصبی در حال رشد، یادگیری رقابتی)
تکامل تفاضلی (دیفرانسیلی)
زندگی مصنوعی
الگوریتم های فرهنگ
سیستم های ایمنی مصنوعی
مدل تکاملی قابل یادگیری
هوش گروهی (SI) یک تکنیک هوش مصنوعی مبنی بر بررسی رفتار جمعی در سیستم های غیر متمرکز و خودسازمانده است . این واژه توسط Wang و Beni در سال 1989 و در مبحث سیستم های رباتی سلولی مطرح شد.
SI معمولا از جمعیتی از عاملهای ساده تشکیل شده که به طور محلی با یکدیگر و محیطشان تعامل دارند. با اینکه ساختار کنترلی متمرکزی برای تحمیل رفتار عاملها وجود ندارد، تعاملات محلی بین عاملها اغلب منجر به بروز یک رفتار سراسری می گردد. مثال:گروه مورچگان، ازدحام پرندگان و دسته حیوانات.
سیستم های نمونه:
ACO:
یک الگوریتم بهینه سازی فرااکتشافی است که می تواند راه حلهای تقریبی را برای مسایل بهینه سازی ترکیبی مشکل بیابد. در ACO، مورچه های مصنوعی با حرکت روی گراف مساله راه حلها را می سازند و با تقلید از مورچه های حقیقی، روی گراف فرومون مصنوعی به جا می گذارند، به نحوی که مورچه های مصنوعی آینده راه حلهای بهتری بیابند. ACO می تواند با موفقیت بر روی مسایل بهینه سازی زیادی اجرا شود.
الگوریتم کلونی مورچه ها:
انسان همیشه برای الهام گرفتن به جهان زنده پیرامون خود نگریسته است. یکی از بهترین طرح های شناخته شده، طرح پرواز انسان است که ابتدا لئورناردو داوینچی(1519-1452) طرحی از یک ماشین پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشین پرنده ای ساخت که دارای موتور بود و بجای بال از ملخ استفاده می کرد.
هم اکنون کار روی توسعه سیستم های هوشمند با الهام از طبیعت از زمینه های خیلی پرطرفدار هوش مصنوعی است. الگوریتمهای ژنتیک که با استفاده از ایده تکاملی داروینی و انتخاب طبیعی مطرح شده، روش بسیار خوبی برای یافتن مسائل بهینه سازیست. ایده تکاملی داروینی بیانگر این مطلب است که هر نسل نسبت به نسل قبل دارای تکامل است و آنچه در طبیعت رخ می دهد حاصل میلیون ها سال تکامل نسل به نسل موجوداتی مثل مورچه است.
الگوریتم کلونی مورچه برای اولین بار توسط دوریگو (Dorigo) و همکارانش به عنوان یک راه حل چند عامله (Multi Agent) برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد.
عامل هوشند(Intelligent Agent) موجودی است که از طریق حسگر ها قادر به درک پیرامون خود بوده و از طریق تاثیر گذارنده ها می تواند روی محیط تاثیر بگذارد.
الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که اخیرا مورد توجه دانشمندان قرار گرفته است.باید تفاوت هوشمندی توده ای(کلونی) و هوشمندی اجتماعی را روشن کنیم.
در هوشمندی اجتماعی عناصر میزانی از هوشمندی را دارا هستند. بعنوان مثال در فرآیند ساخت ساختمان توسط انسان، زمانی که به یک کارگر گفته میشود تا یک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند برای اینکار باید از فرغون استفاده کند نه مثلا بیل!!! نکته دیگر تفاوت سطح هوشمندی افراد این جامعه است. مثلا هوشمندی لازم برای فرد معمار با یک کارگر ساده متفاوت است.
در هوشمندی توده ای عناصر رفتاری تصادفی دارند و بین آن ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند. مثالی در این مورد رفتار موریانه ها در لانه سازیست.
جهت علاقه مند شدن شما به این رفتار موریانه ها وتفاوت هوشمندی توده ای و اجتماعی توضیحاتی را ارائه می دهم :
فرآیند ساخت لانه توسط موریانه ها مورد توجه دانشمندی فرانسوی به نام گرس قرار گرفت. موریانه ها برای ساخت لانه سه فعالیت مشخص از خود بروز می دهند. در ابتدا صدها موریانه به صورت تصادفی به این طرف و آن طرف حرکت می کنند. هر موریانه به محض رسیدن به فضایی که کمی بالاتر از سطح زمین قرار دارد شروع به ترشح بزاق می کنند و خاک را به بزاق خود آغشته می کنند. به این ترتیب گلوله های کوچک خاکی با بزاق خود درست می کنند. علیرغم خصلت کاملا تصادفی این رفتار، نتیجه تا حدی منظم است. در پایان این مرحله در منطقه ای محدود تپه های بسیار کوچک مینیاتوری از این گلوله های خاکی آغشته به بزاق شکل می گیرد. پس از این، همه تپه های مینیاتوری باعث می شوند تا موریانه ها رفتار دیگری از خود بروز دهند. در واقع این تپه ها به صورت نوعی نشانه برای موریانه ها عمل می کنند. هر موریانه به محض رسیدن به این تپه ها با انرژی بسیار بالایی شروع به تولید گلوله های خاکی با بزاق خود می کند. این کار باعث تبدیل شدن تپه های مینیاتوری به نوعی ستون می شود. این رفتار ادامه می یابد تا زمانی که ارتفاع هر ستون به حد معینی برسد. در این صورت موریانه ها رفتار سومی از خود نشان می دهند. اگر در نزدیکی ستون فعلی ستون دیگیری نباشد بلافاصله آن ستون را رها می کنند در غیر این صورت یعنی در حالتی که در نزدیکی این ستون تعداد قابل ملاحظه ای ستون دیگر باشد، موریانه ها شروع به وصل کردن ستونها و ساختن لانه می کنند.
تفاوتهای هوشمندی اجتماعی انسان با هوشمندی توده ای موریانه را در همین رفتار ساخت لانه می توان مشاهده کرد. کارگران ساختمانی کاملا بر اساس یک طرح از پیش تعیین شده عمل می کنند، در حالی که رفتار اولیه موریانه ها کاملا تصادفی است. علاوه بر این ارتیاط مابین کارگران سختمانی مستقیم و از طریق کلمات و ... است ولی بین موریانه ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و از طریق نشانه ها با یکدیگر در تماس اند. گرس نام این رفتار را Stigmergie گذاشت، به معنی رفتاری که هماهنگی مابین موجودات را تنها از طریق تغییرات ایجاد شده در محیط ممکن می سازد.
بهینه سازی مسائل بروش کلونی مورچه(ACO) :
همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در این مسئله فروشنده دوره گرد باید از یک شهر شروع کرده، به شهرهای دیگر برود و سپس به شهر مبدا بازگردد بطوریکه از هر شهر فقط یکبار عبور کند و کوتاهترین مسیر را نیز طی کرده باشد. اگر تعداد این شهرها n باشد در حالت کلی این مسئله از مرتبه (n-1)! است که برای فقط 21 شهر زمان واقعا زیادی می برد:
روز1013*7/1 = S1016*433/2 = ms10*1018*433/2 = !20
با انجام یک الگوریتم برنامه سازی پویا برای این مسئله ، زمان از مرتبه نمایی بدست می آید که آن هم مناسب نیست. البته الگوریتم های دیگری نیز ارائه شده ولی هیچ کدام کارایی مناسبی ندارند. ACO الگوریتم کامل و مناسبی برای حل مسئله TSP است.
مورچه ها چگونه می توانند کوتاهترین مسیر را پیدا کنند؟
مورچه ها هنگام راه رفتن از خود ردی از ماده شیمیایی فرومون(Pheromone) بجای می گذارند البته این ماده بزودی تبخیر می شد ولی در کوتاه مدت بعنوان رد مورچه بر سطح زمین باقی می ماند. یک رفتار پایه ای ساده در مورچه های وجود دارد :
آنها هنگام انتخاب بین دو مسیر بصورت احتمالاتی( Statistical) مسیری را انتخاب می کنند که فرومون بیشتری داشته باشد یا بعبارت دیگر مورچه های بیشتری قبلا از آن عبور کرده باشند. حال دقت کنید که همین یک تمهید ساده چگونه منجر به پیدا کردن کوتاهترین مسیر خواهد شد :
همانطور که در شکل 1-1 می بینیم مورچه های روی مسیر AB در حرکت اند (در دو جهت مخالف) اگر در مسیر مورچه ها مانعی قرار دیهم(شکل 2-1) مورچه ها دو راه برای انتخاب کردن دارند. اولین مورچه ازA می آید و بهC می رسد، در مسیر هیچ فرومونی نمی بیند بنابر این برای مسیر چپ و راست احتمال یکسان می دهد و بطور تصادفی و احتمالاتی مسیر CED را انتخاب می کند. اولین مورچه ای که مورچه اول را دنبال می کند زودتر از مورچه اولی که از مسیر CFD رفته به مقصد می رسد. مورچه ها در حال برگشت و به مرور زمان یک اثر بیشتر فرومون را روی CED حس می کنند و آنرا بطور احتمالی و تصادفی ( نه حتما و قطعا) انتخاب می کنند. در نهایت مسیر CED بعنوان مسیر کوتاهتر برگزیده می شود. در حقیقت چون طول مسیر CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر می شود و در نتیجه مورچه های بیشتری نسبت به مسیر دیگر آنرا طی خواهند کرد چون فرومون بیشتری در آن وجود دارد.
نکه بسیار با اهمیت این است که هر چند احتمال انتخاب مسیر پر فرومون ت توسط مورچه ها بیشتر است ولی این کماکان احتمال است و قطعیت نیست. یعنی اگر مسیر CED پرفرومون تر از CFD باشد به هیچ عنوان نمی شود نتیجه گرفت که همه مورچه ها از مسیرCED عبور خواهند کرد بلکه تنها می توان گفت که مثلا 90% مورچه ها از مسیر کوتاهتر عبور خواهند کرد. اگر فرض کنیم که بجای این احتمال قطعیت وجود می داشت، یعنی هر مورچه فقط و فقط مسیر پرفرومون تر را انتخاب میکرد آنگاه اساسا این روش ممکن نبود به جواب برسد. اگر تصادفا اولین مورچه مسیرCFD(مسیر دورتر) را انتخاب می کرد و ردی از فرومون بر جای می گذاشت آنگاه همه مورچه ها بدنبال او حرکت می کردند و هیچ وقت کوتاهترین مسیر یافته نمی شد. بنابراین تصادف و احتمال نقش عمده ای در ACO بر عهده دارند.
نکته دیگر مسئله تبخیر شدن فرومون بر جای گذاشته شده است. برفرض اگر مانع در مسیر AB برداشته شود و فرومون تبخیر نشود مورچه ها همان مسیر قبلی را طی خواهند کرد. ولی در حقیقت این طور نیست. تبخیر شدن فرومون و احتمال به مورچه ها امکان پیدا کردن مسیر کوتاهتر جدید را می دهند.
1-1
2-1
3-1
4-1
مزیتهای ACO :
همانطور که گقته شد «تبخیر شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پیدا کردن کوتاهترین مسیر را می دهند. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینه سازی می شوند. مثلا در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه ها می توانند پس از مدت کوتاهی مسیر بهینه(کوتاهترین) را بیابند.
کاربردهای ACO :
از کاربردهای ACO می توان به بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد ، اشاره نمود :
1. مسیر یابی داخل شهری و بین شهری
2. مسیر یابی بین پست های شبکه های توزیع برق ولتاژ بالا
3. مسیر یابی شبکه های کامپیوتری
مسیر یابی شبکه های کامپیوتری با استفاده از ACO :
در ابتدا مقدمه ای از نحوه مسیر یابی در شبکه های کامپیوتری را توضیح خواهیم داد :
اطلاعات بر روی شبکه بصورت بسته های اطلاعاتی کوچکی (Packet) منتقل می شوند. هر یک از این بسته ها بر روی شبکه در طی مسیر از مبدا تا مقصد باید از گره های زیادی که مسیریاب (Router) نام دارند عبور می کنند. در داخل هر مسیریاب جدولی قرار دارد تا بهترین و کوتاهترین مسیر بعدی تا مقصد از طریق آن مشخص می شود، بنابر این بسته های اطلاعاتی حین گذر از مسیریاب ها با توجه به محتویات این جداول عبور داده می شوند.
روشی بنام : Ant Colony Routering
ACR پیشنهاد شده که بر اساس ایده کلونی مورچه به بهینه سازی جداول می پردازید و در واقع به هر مسیری با توجه به بهینگی آن امتیاز می دهد. استفاده از ACR به این منظور دارای برتری نسبت به سایر روش هاست که با طبیعت دینامیک شبکه سازگاری دارد، زیرا به عنوان مثال ممکن است مسیری پر ترافیک شود یا حتی مسیر یابی (Router) از کار افتاده باشد و بدلیل انعطاف پذیری که ACO در برابر این تغییرات دارد همواره بهترین راه حل بعدی را در دسترس قرار می دهد.
بهینه سازی گروه ذرات :
PSO الگوریتم بهینه سازی سراسری برای بحث در مورد مسایلی است که در آنها بهترین راه حل به صورت یک نقطه یا سطح در فضای چندبعدی نشان داده می شود. فرضیه ها در این فضا رسم می شوند و با یک سرعت اولیه و کانال ارتباطی بین ذرات شروع می شوند. سپس ذرات در فضای راه حل حرکت می کنند و بعد از هر مهر زمانی، براساس معیار شایستگی، مورد ارزیابی قرار می گیرند. بعد از مدتی ذرات به طرف ذراتی که دارای مقادیر شایستگی بهتر در گروه ارتباطی خودشان هستند، سرعت می گیرند. مزیت اصلی این رویکرد نسبت به سایر استراتژی های کمینه سازی مانند آنیلینگ شبیه سازی شده این است که تعداد زیاد افرادی که گروه ذرات را تشکیل می دهند، تکنیکی بسیار ارتجاعی را برای مساله کمینه سازی محلی به کار می برند.
ذرات دارای دو قابلیت هستند : حافظه مربوط به بهترین موقعیت خود و دانش بهترین موقعیت گروه. افراد یک دسته موقعیتهای خوب را با یکدیگر مبادله می کنند و موقعیت و سرعت خود را برمبنای این موقعیتهای خوب تنظیم می سازند. این ارتباط از دو طریق صورت می گیرد:
بهترین سراسری که برای همه شناخته شده است.
بهترین های همسایه که هر ذره فقط با زیرمجموعه ای از دسته در مورد بهترین موقعیتها ارتباط دارد.
جستجوی پخشی احتمالی :
SDS یک جستجوی سراسری مبنی بر عامل و تکنیک بهینه سازی است که برای مسایلی که تابع هدف می تواند به چندین تابع جزئی مستقل تجزیه شود مناسب است. هر عامل یک فرضیه را نگهداری می کند که به طور مکرر با یک تابع هدف جزئی که به طور تصادفی انتخاب می شود ارزیابی می شود که پارامترهای آن با فرضیه فعلی عامل تعیین می گردد. اطلاعات فرضیه ها از طریق ارتباط بین عاملی در جمعیت پخش می گردد. برخلاف ارتباط stigmergetic مورد استفاده در ACO، در SDS عاملها فرضیه ها را از طریق استراتژی ارتباطی یک به یک، مبادله می کنند. SDS هم الگوریتم جستجو و هم Optimisation قدرتمند و موثری است که به خوبی به بیان ریاضی توصیف می گردد.
کاربرد تکنیکهای مبنی بر هوش گروهی : کنترل خودروهای بدون سرنشین، نقشه برداری نجومی.
EP:
اولین بار در 1960 توسط Lawrence J.Fogel برای تکامل شبیه سازی شده به عنوان یک فرایند یادگیری با هدف تولید هوش مصنوعی به کار رفت. Fogel ماشینهای حالت متناهی را به عنوان پیشگویی کننده به کار برد و آنها را تکامل داد.
امروزه EP برخلاف سایر گویشها، گویشی از محاسبه تکاملی با ساختار (نمایش) غیرثابت است و به سختی از استراتژی های تکاملی شناخته می شود.
عملگر تغییر اصلی در آن جهش است، اعضای یک جمعیت به جای اعضای یک species به عنوان بخشی از species خاص درنظر گرفته می شوند، پس هر والد با استفاده از یک انتخاب بازمانده ( ) یک فرزند تولید می کند.
برنامه نویسی ژنتیک(GP) :
یک متدولوژی خودکار الهام گرفته شده از تکامل زیستی است برای یافتن برنامه های کامپیوتری که الگوریتمی تکاملی را برای بهینه کردن جمعیتی از برنامه های کامپیوتری برحسب چشم انداز شایستگی تعیین شده توسط توانایی برنامه برای انجام وظیفه محاسباتی داده شده به کار می رود.
در ابتدا دستورات برنامه و مقادیر داده در قالب ساختارهای درختی سازماندهی می شدند بنابراین از زبانهایی استفاده می شد که به طور طبیعی دارای چنین ساختارهایی بودند مانند Lisp، اما امروزه برنامه¬های کامپیوتری در GP می توانند با زبانهای متنوعی نوشته شوند.
الگوریتم ژنتیک(Genetic Algorithm - GA) :
تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده میکند.
الگوریتمهای ژنتیک معمولاً به عنوان یک شبیه‌ساز کامپیوتر که در آن جمعیت یک نمونهٔ انتزاعی (کروموزومها) از نامزدهای راه‌حل یک مسأله بهینه‌سازی به راه حل بهتری منجر شود، پیاده‌سازی میشوند. به طور سنتی راه‌حلها به شکل رشته‌هایی از ۰ و ۱ بودند، اما امروزه به گونه‌های دیگری هم پیاده‌سازی شده‌اند.
همانطور که در شکل بالا مشاهده می کنید شمای کلی از نحوهٔ عملکرد این الگوریتم را به شما نشان میدهد. در ادامه به توضیح بیشتری در باره الگوریتم ژنتیک خواهیم پرداخت .
روش جستجوی تکاملی
روش های جستجوی ناآگاهانه ، اگاهانه و متاهیوریستیک برای حل مسائل هوش مصنوعی بسیار کارآمد می‌باشند. همچنین می دانیم که در مورد مسائل بهینه سازی اغلب روش های آگاهانه و ناآگاهانه جوابگوی نیاز ما نخواهند بود. چرا که بیشتر مسائل بهینه سازی در رده مسائل NP قرار دارند. بنابراین نیاز به روش جستجوی دیگری داریم که بتواند در فضای حالت مسائل NP به طرف جواب بهینه سراسری حرکت کند. بدین منظور روش های جستجوی متاهیوریستیک را مطرح می کنیم,این روش های جستجو می‌توانند به سمت بهینگی های سراسری مسئله حرکت کنند. در کنار روش های جستجوی متاهیوریستیکی ، روش های جستجوی دیگری نیز وجود دارند که به روش های تکاملی معروفند. در ادامه با این نوع الگوریتم بیشتر آشنا می شویم.(لازم به ذکر است که در نگاه کاربردی به الگوریتم های ژنتیکی, اولین قدم در فهم آن, تفهیم الگوریتم های تکامل و تفاوت آن با دیگر الگوریتم های مشابه است.)
نظریه داروین
همان طور که در ابتدای مقاله گفته شد ، بر اساس [[نظریه داروین]] نسل هایی که از ویژگی های و خصوصیات برتری نسبت به نسل های دیگر برخوردارند شانس بیشتری نیز برای بقا و تکثیر خواهند داشت و ویژگی ها و خصوصیات برتر آنها به نسل های بعدی آنان نیز منتقل خواهد شد. همچنین بخش دوم نظریه داروین بیان میکند که هنگام تکثیر یک ارگان فرزند ، به تصادف رویدادهایی اتفاق می افتد که موجب تغییر خصوصیات ارگان فرزند میشود و در صورتی که این تغییر فایده‌ای برای ارگان فرزند داشته باشد موجب افزایش احتمال بقای آن ارگان فرزند خواهد شد. در محاسبات کامپیوتری ، بر اساس این نظریه داروین روش هایی برای مسائل بهینه سازی مطرح شدند که همه این روش ها از پردازش تکاملی در طبیعت نشات گرفته اند. ما نیز به این روش های جستجو ، الگوریتم های جستجوی تکاملی می گوییم.
الگوریتم تکاملی
الگوریتم های تکاملی که الهام گرفته از مکانیزم تکامل طبیعی و بنا شده بر اصل انتخاب طبیعی داروین می باشد، در مسائل بهینه سازی و جستجو های تطبیقی مورد استفاده قرار می گیرند. پارامتر های تعریف شده دراین الگوریتم ها شامل مواردی مانند : جمعیت، نحوه نمایش اعضای جمعیت، تابع ارزیابی، تابع انتخاب والدین، عملگر های تکاملی بازترکیبی، جهش و تابع انتخاب بازماندگان می باشد [1]. جمعیت، متشکل از اعضای جمعیت بوده که به هر یک از این اعضاء، کروموزوم گفته می شود. هر کروموزوم بازنمایی از یک راه حل مسئله در غالب ژن ها می باشد. به بیانی هر کروموزوم از تعدادی ژن که کد کننده راه حل مسئله بوده تشکیل شده که مقدار ژن ها بر پایه نوع الگوریتم تکاملی مورد استفاده می تواند باینری، حقیقی و یا حتی از نوع گراف باشد. هر کروموزوم موجود در جمعیت بر پایه تابع ارزیابی مسئله، ارزیابی می شود.
هر کروموزوم بر پایه شایستگی بدست آمده از تابع ارز ی ابی و بر اساس تابع انتخاب والدین، برای احراز پست والدی کاندید می شود. کروموزوم هایی که به عنوان والد در نظر گرفته شده تحت عملگر های بازترکیبی و جهش تولید فرزند می نمایند. در نهایت بر اساس راهکار انتخاب بازماندگان تعدادی از فرزندان و تعدادی از اعضای جمعیت اصلی به عنوان جمعیت جدید انتخاب می شوند. در الگوریتم های تکاملی عموماً جمعیت تمامی نسل ها را ثابت در نظر می گیرند .
جمعیت اولیه به صورت تصادفی انتخاب شده و با اعمال پارامتر های مناسب الگوریتم تکاملی بر روی جمعیت م ی توان به را هحل بهینه مسئله دست یافت . بر مبنای اصل شایسته سالاری داروین، همگرایی کروموزوم ها به راه حل بهینه بوده که این امر در بردارنده مفهوم تکامل می باشد. قابل توجه است که چون الگوریتم های تکاملی از نوع جستج و های خلاقانه در فضای جستجو بوده و تمامی فضای جستجو مورد ارزیابی و کاوش قر ار نمی گیرد، تظمینی برای یافتن بهینه سراسری وجود ندارد .
بر اساس نوع نمایش ژن ها، عملگر های بازترکیبی و جهش مختلفی معرفی شده است . در کروموزوم هایی که نمایش ژن ها به صورت اعداد حقیقی است می توان از عملگر های تکاملی مانند عملگر های ریاضی استفاده نمود . در شکل زیر نمونه ای از عملگر بازترکیبی ریاضی ساده نشان داده شده است.
بازترکیبی از نوع ریاضی ساده با ضریب 0,5
عملگر بازترکیبی برا ی اعداد حق یقی، با ترکیب اطلاعات موجود در والدین، امکان جستجو در فضای بین والدین را امکان پذیر م ی نمای د. با اعمال بازترکیبی می توان در اطراف راه حل والدین به جستجو برای یافتن جواب بهینه پرداخت . عملگر جهش بر روی یک کروموزوم اعمال شده و امکان جستجو در تمامی فضای موجود در فضای جستجو را امکان پذیر می نماید. با عملگر جهش امکان جستجو در فضا های جدید وجود دارد.
انواع مختلف الگوریتم های تکاملی
انواع مختلف الگوریتم های تکاملی که تا بحال مطرح شده اند، به شرح زیر میباشد :
Genetic Algorithm
Genetic Programming
Evolutionary Strategies
Evolutionary Programming
Differential Evolution
Cultural Evolution
Co-evolution
الگوریتمهای تکاملی به سه دسته اصلی تقسیم می شوند:
الگوریتم ژنتیک
استراتژیهای تکاملی
برنامه ریزی تکاملی
الگوریتم ژنتیک
الگوریتم های ژنتیک یکی از الگوریتم های جستجوی تصادفی است که ایده آن برگرفته از طبیعت میباشد . الگوریتم های ژنتیک در حل مسائل بهینه سازی کاربرد فراوانی دارند . به عنوان مثال می‌توان به مسئله فروشنده دوره گرد اشاره کرد.(در ادامه با این مسئله و حل آن بیشتر آشنا می شویم) در طبیعت از ترکیب کروموزوم های بهتر ، نسل های بهتری پدید می‌آیند . در این بین گاهی اوقات جهش هایی نیز در کروموزوم ها روی میدهد که ممکن است باعث بهتر شدن نسل بعدی شوند. الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل مسائل میکند .
الگوریتم ژنتیک که به‌عنوان یکی از روشهای تصادفی بهینه یابی شناخته شده, توسط جان هالند در سال ۱۹۶۷ ابداع شده‌است. بعدها این روش با تلاشهای گلدبرگ ۱۹۸۹, مکان خویش را یافته و امروزه نیز بواسطه تواناییهای خویش , جای مناسبی در میان دیگر روشها دارد. روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار میباشد. این روش , بر مبنای نظریه تکامل تدریجی و ایده‌های بنیادین داروین پایه گذاری شده‌است.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده میشود مجموعه‌ای از پارامترهای هدف بصورت اتفاقی تولید میشود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می‌دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می‌کنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل می‌دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد.
در تعریفی دیگر الگوریتم ژنتیک یکی از الگوریتمهای تکاملی است که اگرچه به شکلهای مختلفی ارائه شده است اما پایه تمام این شکلها چهار فرایند است که در ادامه به آنها پرداخته می شود. الگوریتم ژنتیک یک بهینه سازی غیر جبری است که مناسب برای توابعی است که بهینه سازی آنها با روشهای جبری کاری طاقت فرسا است. الگوریتم ژنتیک برای مسایلNP-Hard بسیار مناسب می باشد. همچنین این الگوریتمها قادر به حل مسایلی هستند که در فضای حلشان ناپیوستگی وجود دارد. یکی دیگر از مزایای این روش، توانایی اعمال آن به مسایلی است که دارای متغیرهای زیاد می باشند.
از طرف دیگر، الگوریتم ژنتیک ضعفهایی نیز دارد. این روش غیر جبری است بنابراین پاسخ دقیق مساله را نمی یابد و حتی ممکن است برای یک مساله مشخص با هر بار بکارگیری پاسخی متفاوت ارائه دهد. اگرچه تمامی این پاسخها می توانند پاسخهایی باشند که دقت مورد نیاز را برآورده کنند. الگوریتمهای ژنتیک قابل اعمال به تمام مسایل بهینه سازی هستند اما در مسایلی این روشها نسبت به سایر روشها بسیار کندتر عمل می کنند. بنابراین ژنتیک، روشی عمومی برای تمام جستجوها نمی باشد.
با این وجود این الگوریتم (و سایر الگوریتمهای تکاملی) فضای پاسخ را به صورت موازی و خوشه به خوشه و نه به صورت عضو به عضو می کاوند به همین دلیل امکان رخ دادن اپتیمم های محلی از بین می رود. این روشها نیازی به اطلاعات مربوط به مشتقات تابع هدف ندارند. تنها شکل اصلی تابع مورد نیاز می باشد.
چهار فرایند اصلی در الگوریتم ژنتیک عبارتند از :
ایجاد جمعیت کروموزومها (تبدیل مجموعه ای از پاسخهای ممکن به شکل کروموزوم و ژن
انتخاب (جفت یابی) (Selection)
ترکیب (CrossOver)
جهش (Mutation)
در شکل چگونگی مراحل الگوریتم ژنتیک، نشان داده شده است.
قبل از ادامه بحث لازم است قسمتی بسیار مهم از الگوریتم ژنتیک، تابع تطابق یا تابع هدف (Fitness function - Objective function) را معرفی کنیم. این تابع شاید قلب الگوریتم ژنتیک باشد. انتخاب اعضاء بهتر یا به عبارتی زنده ماندن ژنهای بهتر با این تابع کنترل می شود.
الگوریتمهای ژنتیک اگرچه در شکلهای مختلفی وجود دارند اما حداقل شامل چهار قسمت زیر می باشند:
• جمعیتی از جوابهای ممکن که به کروموزوم و ژن تبدیل شده اند.
• عملگر انتخاب
• عملگر ترکیب
• عملگر جهش
طراحی یک الگوریتم ژنتیک برای مساله ای خاص دارای سه مرحله است:
• طراحی شیوه کدگذاری
• طراحی تابع تطابق
• طراحی عملگرهای ژنتیک
در ادامه هر کدام از این عناصر مورد بررسی قرار می گیرد.
عملگرهای یک الگوریتم ژنتیک
در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است: اول روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. به شکل سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسه ها.نمایش داده میشود.دوم روشی لازم است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ میتواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود, که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری میشود.
فرضیه با جمعیتی کاملاً تصادفی منحصر بفرد آغاز میشود و در نسلها ادامه می‌یابد. در هر نسل گنجایش تمام جمعیت ارزیابی میشود، چندین فرد منحصر در فرایندی تصادفی از نسل جاری انتخاب میشوند (بر اساس شایستگیها) و برای شکل دادن نسل جدید، اصلاح میشوند (کسر یا دوباره ترکیب میشوند) و در تکرار بعدی الگوریتم به نسل جاری تبدیل میشود.
کدگذاری و نحوه نمایش
نحوه نمایش جواب مسئله و ژن ها در موفقیت الگوریتم و نحوه پیاده سازی الگوریتم ژنتیک تاثیر بسیار مهمی دارد. در بیشتر مسائل نیز روش های مختلفی برای نشان دادن جواب مساله می‌توان طراحی کرد. به عنوان مثال در مسئله 8 وزیر به جای استفاده از بردار( آرایه یک بعدی ) 8 عنصری می‌توان از یک ماتریس 8 * 8 استفاده کرد که در آن هر وزیر میتواند در هریک از 64 خانه صفحه شطرنج قرار گیرد. هنگام استفاده از این روش نمایش ، در یک خانه ممکن است بیش از یک وزیر قرار گیرد بنابراین هنگام پیاده سازی الگوریتم باید از بروز چنین مسئله‌ای جلوگیری کنیم.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 46 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله پردازش تکاملی والگوریتم تکاملی
