پایان نامه درمورد مورچه، مورچه‌ها، ، غذا، -، کلونی، هوشمندی، (1)

کارها
پس کدنویسی و اجرای مساله در نرم افزار GAMS و روی یک لپتاپ با مشخصات Intel®Core i7 2.00GHz 8.00GB RAM &و با سیستم عامل ویندوز 7، 64 بیتی اجرا شده است. جواب زیر حاصل شده است که نمای شماتیک آن در زیر آمده است. مدل با ابعاد بزرگتر نیز مورد برازش قرار گرفته است که نتایج آن در پیوست ارائه شده است.
14732002024380نمودار (1) – نحوه قرار گیری جواب مساله
00نمودار (1) – نحوه قرار گیری جواب مساله
594995-171450
3-2-2.روش های فرا ابتکارییک روش ناشیانه برای حل مسائل بهینه‌سازی ترکیبی این است که تمامی جواب‌های امکان‌پذیر در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهایت، بهترین جواب انتخاب گردد. روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منتهی می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن غیرممکن است. با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است. در این زمینه، الگوریتم‌های مختلفی به وجود آمده است که مشهورترین نمونه آنها، روش سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کرانه برای حل برنامه‌های خطی با متغیرهای صحیح است. برای مسائلی با ابعاد بزرگ، روش سیمپلکس از کارایی بسیار خوبی برخوردار است، ولی روش شاخه و حد کارایی خود را از دست می‌دهد و عملکرد بهتری از شمارش کامل نخواهد داشت. به دلایل فوق، اخیراً تمرکز بیشتری بر روش‌های ابتکاری (Heuristic) یا فرا ابتکاری (Metaheuristic) یا جستجوی تصادفی (Random Method) صورت گرفته است. روش‌های جستجوی ابتکاری، روش‌هایی هستند که می‌توانند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کنند. روش‌های جستجوی ابتکاری عمدتاً بر مبنای روش‌های شمارشی می‌باشند، با این تفاوت که از اطلاعات اضافی برای هدایت جستجو استفاده می‌کنند. این روش‌ها از نظر حوزه کاربرد، کاملاً عمومی هستند و می‌توانند مسائل خیلی پیچیده را حل کنند. عمده این روش‌ها، تصادفی بوده و از طبیعت الهام گرفته شده‌اند.
3-2-2-1. الگوریتم مورچگان3-2-2-1-1. مقدمهالگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه ها است. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه‌ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه‌ها دارای نوعی هوشمندی توده‌ای است که اخیراً مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچه‌ها ابتدا به طور تصادفی به این سو و آن سو می‌روند تا غذا بیابند. سپس به لانه بر می‌گردند و ردّی از فرومون به جا می‌گذارند. چنین ردهایی پس از باران به رنگ سفید در می‌آیند و قابل رویتاند. مورچه‌های دیگر وقتی این مسیر را می‌یابند، گاه پرسه زدن را رها کرده و آن را دنبال می‌کنند. سپس اگر به غذا برسند به خانه بر می‌گردند و رد دیگری از خود در کنار رد قبل می‌گذارند و به عبارتی مسیر قبل را تقویت می‌کنند. فرومون به مرور تبخیر می‌شود که از سه جهت مفید است:
باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه‌های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر (بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر.
اگر فرومون اصلاً تبخیر نمی‌شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذّاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند.
وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند.
لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را از خانه تا غذا بیابد بقیه مورچه‌ها به احتمال زیادی همان مسیر را دنبال می‌کنند و با تقویت مداوم آن مسیر و تبخیر ردهای دیگر، به مرور همه مورچه‌ها هم مسیر می‌شوند. هدف الگوریتم مورچه‌ها تقلید این رفتار توسط مورچه‌هایی مصنوعی است که روی نمودار در حال حرکت اند. مساله یافتن کوتاه‌ترین مسیر است و حلالش این مورچه‌های مصنوعی اند.
14522451675765شکل (1) – نحوه حرکت مورچه ها روی مسیر
00شکل (1) – نحوه حرکت مورچه ها روی مسیر
60706037465
تبخیر شدن فرومون و احتمال تصادف به مورچه‌ها امکان پیدا کردن کوتاهترین مسیر را می‌دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینهسازی می‌شوند. مثلاً در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره‌ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره‌ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه‌ها می‌توانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند.
3-2-2-1-2. مزیتهای ACOهمانطور که گقته شد «تبخیر شدن فرومون» و «احتمال تصادف» به مورچه ها امکان پیدا کردن کوتاهترین مسیر را می دهند. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینه سازی می شوند. مثلا در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه ها می توانند پس از مدت کوتاهی مسیر بهینه(کوتاهترین) را بیابند.
3-2-2-1-3. کاربردهای ACOاز کاربردهایACO می توان به بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد ، اشاره نمود :
مسیر یابی داخل شهری و بین شهری
مسیر یابی بین پست های شبکه های توزیع برق ولتاژ بالا
مسیر یابی شبکه های کامپیوتری
3-2-2-1-4. الگوریتم ACO
برای پیاده سازی کلونی مورچه، از مورچه های مصنوعی به عنوان عناصری در بهینه سازی استفاده می شود. البته این عناصر تفاوتهای اساسی با مورچه های واقعی دارند که عبارتند از:
حافظه: برای مورچه های مصنوعی می توان یک حافظه در نظر گرفت که مسیرهای حرکت را در خود نگه می دارند.
موانع ساختگی: تغییر دادن جزئیات مسئله برای بررسی الگوریتم و رسیدن به جوابهای متنوع.
حیات در محیط گسسته: مورچههای واقعی نمیتوانند جدا از کلونی به حیات خود ادامه دهند.
توجه به کولونی مورچه‌ها و نیز استفاده وسیع ازآن بیشتر ناشی از توجه خاصی بوده که پیشتر، بیولوژیست‌ها به کولونی مورچه‌ها داشته‌اند. چه بسا سیستم‌های دیگر طبیعی نیز باشند که تاکنون مورد مطالعه قرار نگرفته‌اند یا اگرهم مطالعه شده‌اند با دید معطوف به هوشمندی و بهینه‌سازی نبوده است.
   بنابراین می‌توان تصور کرد که در سال‌های آینده روش‌های زیاد دیگری جهت بهینه‌سازی و نیز کنترل هوشمند با استفاده از سیستم‌های طبیعی پیشنهاد شوند . تا به حال به کرات به مزایای این نوع هوشمندی اشاره کرده‌ایم اما اکنون بار دیگر تأکید می‌کنیم که این نوع از هوشمندی علاوه بر تمامی مزایای مهندسی، یک مزیت عمده و اصلی دارد: تمامی این روش‌ها قابلیت تعمق زیستی دارند به این معنی که طبیعت آنها را در طی میلیون‌ها سال به عنوان روش بهینه انتخاب کرده است.
3-2-2-2. الگوریتم ژنتیک3-2-2-2-1. مقدمه محدوده کاری الگوریتم ژنتیک بسیار وسیع میباشد و هر روز با پیشرفت روز افزون علوم و تکنولوژی استفاده از این روش در بهینهسازی و حل مسائل بسیار گسترش یافته است. الگوریتم ژنتیک یکی از زیر مجموعههای محاسبات تکامل یافته می باشد که رابطه مستقیمی با مبحث هوش مصنوعی دارد در واقع الگوریتم ژنتیک یکی از زیر مجموعههای هوش مصنوعی می باشد. الگوریتم ژنتیک را میتوان یک روش جستجوی کلی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید میکند. الگوریتم ژنتیک برروی یکسری از جوابهای مساله به امید بدست آوردن جوابهای بهتر قانون بقای بهترین را اعمال میکند. درهر نسل به کمک فرآیند انتخابی متناسب با ارزش جوابها و تولید مثل جوابهای انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شدهاند، تقریبهای بهتری از جواب نهایی بدست میآید. این فرایند باعث میشود که نسلهای جدید با شرایط مساله سازگارتر باشد.
الگوریتم ژنتیک (Genetic Algorithm – GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی مانند وراثت و جهش

متن کامل در سایت homatez.com