پایان نامه درمورد مورچه، مورچه‌ها، ، غذا، -، کلونی، هوشمندی، (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

About: admin