3-5-انواع روش‌هاي فرا ابتكاري برگرفته از طبيعت
1-3-5-الگوريتم ژنتيك
الگوريتم ژنتيك (Genetic Algorithm) روشي عمومي از روش‌هاي فرا ابتكاري براي بهينه‌سازي گسسته ميباشد كه مسائل جدول زمانبندي را حل مي‌نمايد. روش شبيه‌سازي كه در ادامه مورد بحث قرار می‌گيرد، راهبرد تكاملي نام دارد. اين روش در سال 1975 به وسيله هولند (Holland) و در سال 1989 توسط گولدبرگ (Goldberg) ابداع شده است.
اين روش نوعي روش جستجوي همسايه است كه عملكردي مشابه ژن دارد. در طبيعت، فرايند تكامل هنگامي ايجاد ميشود كه چهار شرط زير برقرار باشد:
الف) يك موجود توانايي تكثير داشته باشد (قابليت توليد مثل).
ب) جمعيتي از اين موجودات قابل تكثير وجود داشته باشد.
پ) چنين وضعيتي داراي تنوع باشد.
ت) اين موجودات به وسيله قابليت‌هايي در زندگي از هم جدا شوند.
در طبيعت، گونه‌هاي متفاوتي از يك موجود وجود دارند كه اين تفاوت‌ها در كروموزوم‌هاي اين موجودات ظاهر ميشود و باعث تنوع در ساختار و رفتار اين موجودات ميشود.
اين تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثير مي‌گذارد. موجوداتي كه قابليت‌ها و توانايي بيشتري براي انجام فعاليت‌ها در محيط دارند (موجودات متكامل‌تر)، داراي نرخ زاد و ولد بالاتري خواهند بود و طبعاً موجوداتي كه سازگاري كمتري با محيط دارند، از نرخ زاد و ولد پايين‌تري برخوردار خواهند بود. بعد از چند دوره زماني و گذشت چند نسل، جمعيت تمايل دارد كه موجوداتي را بيشتر در خود داشته باشد كه كروموزوم‌هايشان با محيط اطراف سازگاري بيشتري دارد.
در طي زمان، ساختار افراد جامعه به علت انتخاب طبيعي تغيير مي‌كند و اين نشانه تكامل جمعيت است.
6- آنيلينگ شبيه‌سازي شده
اين روش توسط متروپوليس (Metropolis) و همكاران در سال 1953 پيشنهاد شده و جهت بهينه‌سازي به وسيله وچی (Vecchi)، گلات (Gelatt) و کرک‌پاتريک (kirkpatrick ) در سال 1983 مورد بازبيني قرار گرفته است. اين روش در مسائل تاكسي تلفني كاربرد دارد.
الگوريتم آنيلينگ شبيه‌سازي شده (Simulated Annealing) در شکل عمومي، بر اساس شباهت ميان سرد شدن جامدات مذاب و حل مسائل بهينه‌سازي تركيبي به وجود آمده است. در فيزيك مواد فشرده، گرم و سرد كردن فرايندي است فيزيكي كه طي آن يك ماده جامد در ظرفي حرارت داده ميشود تا مايع شود؛ سپس حرارت آن بتدريج كاهش مي‌يابد. بدين ترتيب تمام ذرات فرصت مي‌يابند تا خود را در پايين‌ترين سطح انرژي منظم كنند. چنين وضعي در شرايطي ايجاد ميشود كه گرمادهي كافي بوده و سرد كردن نيز به آهستگي صورت گيرد. جواب حاصل از الگوريتم گرم و سرد كردن شبيه‌سازي شده، به جواب اوليه وابسته نيست و مي‌توان توسط آن جوابي نزديك به جواب بهينه به دست آورد. حد بالايي زمان اجراي الگوريتم نيز قابل تعيين است. بنابراين الگوريتم گرم و سرد كردن شبيه‌سازي شده، الگوريتمي است تكراري كه اشكالات روش‌هاي عمومي مبتني بر تكرار را ندارد.
در روش آنيلينگ شبيه‌سازي شده، به صورت پي در پي از جواب جاري به يكي از همسايه‌هاي آن انتقال صورت مي‌گيرد. اين سازوکار توسط زنجيره ماركوف به صورت رياضي قابل توصيف است. در اين روش، يك مجموعه آزمون انجام مي‌گيرد؛ اين آزمون‌ها به نحوي است كه نتيجه هر يك به نتيجه آزمون قبل وابسته است. در روش آنيلينگ شبيه‌سازي شده، منظور از يك آزمون، انتقال به نقطه جديد است و روشن است كه نتيجه انتقال به نقطه جديد تنها وابسته به مشخصات جواب جاري است.
روش جستجوي همسايه و روش آنيلينگ شبيه‌سازي شده، هر دو روش‌هاي تكراري هستند. در الگوريتم آنيلينگ شبيه‌سازي شده، هر بار كه شاخص كنترل‌كننده به مقدار نهايي خود مي‌رسد، در حقيقت يك عمليات تكراري انجام شده است. در الگوريتم جستجوي همسايه، هنگامي كه تعداد تكرارها به سمت بي‌نهايت ميل مي‌كند، روش به جواب بهينه نزديك ميشود. اما عملكرد الگوريتم آنيلينگ شبيه‌سازي شده سريع‌تر است.
7-شبکه‌های عصبی
شبکه‌های عصبی (Neural Networks) مصنوعی سيستم‌هاي هوشمندی هستند که از شبکه‌هاي عصبي طبيعي الهام گرفته شده‌اند. شبکه‌هاي عصبي مصنوعي در واقع تلاشي براي حرکت از سمت مدل محاسباتي فون نيومن به سمت مدلي است که با توجه به عملکرد و ويژگي‌هاي مغز انسان طراحي شده است. مدل فون نيومن گرچه هم اکنون بسيار استفاده میشود، اما از کمبودهايي رنج مي‌برد که تلاش شده است اين کمبودها در شبکه‌هاي عصبي مصنوعي برطرف شود.
در سال 1943 مدلی راجع به عملکرد نورون‌ها (Neuron) نوشته شد که با اندکی تغيير، امروزه بلوک اصلی سازنده اکثر شبکه‌های عصبی مصنوعی می‌باشد. عملکرد اساسی اين مدل مبتنی بر جمع کردن ورودی‌ها و به دنبال آن به وجود آمدن يک خروجی است. ورودی‌های نورون‌ها از طريق دنريت‌ها که به خروجی نورون‌های ديگر از طريق سيناپس متصل است، وارد می‌شوند. بدنه سلولی کليه اين ورودی‌ها را دريافت میکند و چنانچه جمع اين مقادير از مقداری که به آن آستانه گفته میشود بيشتر باشد، در اصطلاح برانگيخته شده يا آتش میکند و در اين صورت، خروجی نورون روشن يا خاموش خواهد شد.
مدل پايه‌اي نورون به صورت شکل 1-3 تعريف میشود.
اين مدل و برخی از کارهای مربوط به آن را بايد به عنوان شروع مطالعات تحليلی در نظر گرفت. گر چه اين مدل ساده فاقد ويژگی‌های پيچيده بدنه سلولی نورون‌های بيولوژيکی است، اما میتوان به آن به صورت مدلی ساده از آنچه که واقعاً موجود است نگريست.
جستجوي ممنوع
روشی عمومي است كه به وسيله گلوور (Glover) در سال 1989 پيشنهاد شده و در حل مسائل برنامه‌ريزي كاري ـ خريد کاربرد دارد.
روش جستجوي ممنوع (Tabu Search)، همانند روش آنيلينگ شبيه‌سازي شده بر اساس جستجوي همسايه بنا شده است. در اين روش عملكرد حافظه انسان شبيه‌سازي شده است. حافظه انسان با به كارگيري ساختماني مؤثر و در عين حال ساده از اطلاعات، آنچه را در قبل رؤيت شده، ذخيره مي‌كند. اين مركز همچنين فهرستی از حركات منع شده را تنظيم مي‌كند و اين فهرست همواره بر اساس آخرين جستجوها منظم ميشود. اين روش از انجام هر گونه عمليات مجدد و تكراري جلوگيري مي‌كند.
شكل نوين جستجوي ممنوع توسط گلوور مطرح شده است. روش جستجوي مبتني بر منع، با ايجاد تغييري كوچك در روش جستجوي همسايه به وجود مي‌آيد. هدف اين روش آن است كه بخش‌هايي از مجموعه جواب كه پيش از اين بررسي نشده است، مد نظر قرار گيرد. بدين منظور حركت به جواب‌هايي كه اخيراً جستجو شده، ممنوع خواهد بود.
ساختار كلي روش جستجوي ممنوع بدين صورت است كه ابتدا يك جواب اوليه امكان‌پذير انتخاب ميشود؛ سپس براي جواب مربوط، بر اساس يک معيار خاص مجموعه‌اي از جواب‌هاي همسايه امكان‌پذير در نظر گرفته ميشود.
در گام بعد، پس از ارزيابي جواب‌هاي همسايه تعيين شده، بهترين آنها انتخاب ميشود و جابه‌جايي از جواب جاري به جواب همسايه انتخابي صورت مي‌گيرد. اين فرايند به همين ترتيب تكرار ميشود تا زماني كه شرط خاتمه تحقق يابد.
در روش جستجوي ممنوع، فهرستي وجود دارد كه جابه‌جايي‌هاي منع شده را نگهداري مي‌كند و به فهرست تابو معروف است و كاربرد اصلي آن، پرهيز از همگرا شدن به جواب‌هاي بهينه محلي است. به عبارت ديگر، به كمك فهرست تابو جابه‌جايي به جواب‌هايي كه اخيراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هايي از مجموعه جواب كه پيش از اين مورد بررسي قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جايي از جواب جاري به جواب همسايه امكان‌پذير زماني انجام ميشود كه در فهرست تابو قرار نداشته باشد. در غير اين صورت، جواب همسايه ديگري كه در ارزيابي جواب‌هاي همسايه در رده بعدي قرار گرفته است، انتخاب شده و جابه‌جايي به آن صورت مي‌گيرد.
در روش جستجوي ممنوع بعد از هر جابه‌جايي، فهرست تابو بهنگام ميشود، به نحوي كه جابه‌جايي جديد به آن فهرست اضافه شده و جابه‌جايي كه تا n تكرار مشخص در فهرست بوده است، از آن حذف ميشود. نحوه انتخاب ميتواند با توجه به شرايط و نوع مسأله متفاوت باشد.
سيستم مورچه (Ant System)
اين روش در سال 1991 توسط مانيه‌زو (Maniezzo) دوريگو (Dorigo) و کولورنی (Colorni) پيشنهاد شده است كه در حل مسأله فروشنده دوره‌گرد و مسائل تخصيص چندوجهي کاربرد دارد.
الگوريتم بهينه‌سازي كلوني مورچه‌ها از عامل‌هاي ساده‌اي كه مورچه ناميده مي‌شوند، استفاده مي‌كند تا به صورت تكراري جواب‌هايي توليد كند. مورچه‌ها میتوانند كوتاه‌ترين مسير از يك منبع غذايي به لانه را با بهره‌گيري از اطلاعات فرموني پيدا کنند. مورچه‌ها در هنگام راه رفتن، روي زمين فرمون مي‌ريزند و با بو كشيدن فرمون ريخته شده بر روي زمين راه را دنبال مي‌كنند؛ چنانچه در طي مسير به سوي لانه به يك دوراهي برسند، از آن جايي كه هيچ اطلاعي درباره راه بهتر ندارند، راه را به تصادف برمي‌گزينند. انتظار مي‌رود به طور متوسط نيمي از مورچه‌ها مسير اول و نيمي ديگر مسير دوم را انتخاب كنند.
فرض ميشود كه تمام مورچه‌ها با سرعت يكسان مسير را طي كنند. از آنجا كه يك مسير كوتاه‌تر از مسير ديگر است، مورچه‌هاي بيشتري از آن مي‌گذرند و فرمون بيشتري بر روي آن انباشته ميشود. بعد از مدت كوتاهي مقدار فرمون روي دو مسير به اندازه‌اي مي رسد كه روي تصميم مورچه‌هاي جديد براي انتخاب مسير بهتر تأثير مي‌گذارد. از اين به بعد، مورچه‌هاي جديد با احتمال بيشتري ترجيح مي‌دهند از مسير كوتاه‌تر استفاده كنند، زيرا در نقطه تصميم‌گيري مقدار فرمون بيشتري در مسير كوتاه‌تر مشاهده مي‌كنند. بعد از مدت كوتاهي تمام مورچه‌ها اين مسير را انتخاب خواهند كرد.
مقدمه ای بر بهینه سازی و الگوریتم های موجود
هدف از بهينه‌سازي يافتن بهترين جواب قابل قبول، با توجه به محدوديت‌ها و نيازهاي مسأله است. براي يك مسأله، ممكن است جواب‌هاي مختلفي موجود باشد كه براي مقايسه آنها و انتخاب جواب بهينه، تابعي به نام تابع هدف تعريف ميشود. انتخاب اين تابع به طبيعت مسأله وابسته است. به عنوان مثال، زمان سفر يا هزينه از جمله اهداف رايج بهينه‌سازي شبكه‌هاي حمل و نقل ميباشد. به هر حال، انتخاب تابع هدف مناسب يكي از مهمترين گام‌هاي بهينه‌سازي است. گاهي در بهينه‌سازي چند هدف به طور همزمان مد نظر قرار مي‌گيرد؛ اين گونه مسائل بهينه‌سازي را كه دربرگيرنده چند تابع هدف هستند، مسائل چند هدفي مي‌نامند. ساده‌ترين راه در برخورد با اين گونه مسائل، تشكيل يك تابع هدف جديد به صورت تركيب خطي توابع هدف اصلي است كه در اين تركيب ميزان اثرگذاري هر تابع با وزن اختصاص يافته به آن مشخص ميشود. هر مسأله بهينه‌سازي داراي تعدادي متغير مستقل است كه آنها را متغيرهاي طراحي می‌نامند كه با بردار n بعدي x نشان داده مي‌شوند.
هدف از بهينه‌سازي تعيين متغيرهاي طراحي است، به گونه‌اي كه تابع هدف كمينه يا بيشينه شود.
مسائل مختلف بهينه‌سازي به دو دسته زير تقسيم ميشود:
الف) مسائل بهينه‌سازي بي‌محدوديت: در اين مسائل هدف، بيشينه يا كمينه كردن تابع هدف بدون هر گونه محدوديتي بر روي متغيرهاي طراحي ميباشد.
ب) مسائل بهينه‌سازي با محدوديت: بهينه‌سازي در اغلب مسائل كاربردي، با توجه به محدوديت‌هايي صورت مي‌گيرد؛ محدوديت‌هايي كه در زمينه رفتار و عملكرد يك سيستم ميباشد و محدوديت‌هاي رفتاري و محدوديت‌هايي كه در فيزيك و هندسه مسأله وجود دارد، محدوديت‌هاي هندسي يا جانبي ناميده مي‌شوند.
معادلات معرف محدوديت‌ها ممكن است به صورت مساوي يا نامساوي باشند كه در هر مورد، روش بهينه‌سازي متفاوت ميباشد. به هر حال محدوديت‌ها، ناحيه قابل قبول در طراحي را معين مي‌كنند.
فرايند بهينه سازي
فرموله كردن مسئله: در اين مرحله، يك مسئله ي تصميم گيري، همراه با يك ساختار كلي از آن تعريف ميشود. اين ساختار كلي ممكن است خيلي دقيق نباشد اما وضعيت كلي مسئله را، كه شامل فاكتورهاي ورودي و خروجي و اهداف مسئله است، بيان مي كند. شفاف سازي و ساختاردهي به مسئله، ممكن است براي بسياري از مسايل بهينه سازي، كاري پيچيده باشد.
مدل سازي مسئله:
در اين مرحله يك مدل رياضي كلي براي مسئله، ساخته مي شود. مدلسازي ممكن است از مدل هاي مشابه در پيشينه ي موضوع كمك بگيرد. اين گام موجب تجزيه مسئله به يك يا چند مدل بهينه‌سازي مي گردد.
بهينه سازي مسئله:
پس از مدل سازي مسئله، روال حل، يك راه حل خوب براي مسئله توليد مي كند. اين راهحل ممكن است بهينه يا تقريباً بهينه باشد. نكته اي كه بايد به آن توجه داشت اين است كه راه حل به دست آمده، راه حلي براي مدل طراحي شده است، نه براي مسئله ي واقعي. در هنگام فرموله كردن و مدلسازي ممكن است تغييراتي در مسئله واقعي به وجود آمده و مسئله ي جديد، نسبت به مسئله ي واقعي تفاوت زيادي داشته باشد.
استقرار مسئله:
راه حل به دست آمده توسط تصميم گيرنده بررسي مي شود و در صورتي كه قابل قبول باشد، مورد استفاده قرار مي گيرد و در صورتي كه راهحل قابل قبول نباشد، مدل يا الگوريتم بهينه سازي بايد توسعه داده شده و فرايند بهينه سازي تكرار گردد.
الگوریتم های بهینه سازی
هدف الگوریتم های اکتشافی، ارائه راه حل در چارچوب یک زمان قابل قبول است که برای حل مسئله مناسب باشد، ممکن است الگوریتم اکتشافی، بهترین راه حل واقعی برای حل مسئله نبوده ولی می تواند راه حل نزدیک به بهترین باشد. الگوریتم های اکتشافی با الگوریتم های بهینه سازی برای اصلاح کارایی الگوریتم میتوانند ترکیب شوند. الگوریتم فرا اکتشافی ترکیبی است از الگوریتم های اکتشافی که برای پیدا کردن، تولید یا انتخاب هر اکتشاف در هر مرحله طراحی میشود و راه حل خوبی برای مسائلی که مشکل بهینهسازی دارند ارائه می‌دهد. الگوریتم های فرا اکتشافی برخی از فرضیات مسائل بهینه سازی که باید حل شود را در نظر می گیرد.
روش‌هاي فرا ابتكاري برگرفته از طبيعت
الگوريتم هاي فراابتكاري الگوريتم هايي هستند كه با الهام از طبيعت، فيزيك و انسان طراحي شده اند و در حل بسياري از مسايل بهينه سازي استفاده می شوند. معمولاً از الگوريتم هاي فراابتكاري در تركيب با ساير الگوريتم ها، جهت رسيدن به جواب بهينه يا خروج از وضعيت جواب بهينه محلي استفاده ميگردد. در سال‌هاي اخير يكي از مهمترين و اميدبخش‌ترين تحقيقات، «روش‌هاي ابتكاري برگرفته از طبيعت» بوده است؛ اين روش‌ها شباهت‌هايي با سيستم‌هاي اجتماعي و يا طبيعي دارند. كاربرد آنها برگرفته از روش‌هاي ابتكاري پيوسته می‌باشد كه در حل مسائل مشكل تركيبي (NP-Hard) نتايج بسيار خوبی داشته است.
در ابتدا با تعريفي از طبيعت و طبيعي بودن روش‌ها شروع مي‌كنيم؛ روش‌ها برگرفته از فيزيك، زيست‌شناسي و جامعه‌شناسي هستند و به صورت زير تشكيل شده‌اند:
– استفاده از تعداد مشخصي از سعي‌ها و كوشش‌هاي تكراري
– استفاده از يك يا چند عامل (نرون، خرده‌ريز، كروموزوم، مورچه و غيره)
– عمليات (در حالت چند عاملي) با يك سازوکار همكاري ـ رقابت
– ايجاد روش‌هاي خود تغييري و خود تبديلي
طبيعت داراي دو تدبير بزرگ ميباشد:
1- انتخاب پاداش براي خصوصيات فردي قوي و جزا براي فرد ضعيف‌تر؛
2- جهش كه معرفي اعضای تصادفي و امکان تولد فرد جديد را ميسر می‌سازد.
به طور كلي دو وضعيت وجود دارد كه در روش‌هاي ابتكاري برگرفته از طبيعت ديده ميشود، يكي انتخاب و ديگري جهش. انتخاب ايده‌اي مبنا براي بهينه‌سازي و جهش ايده‌اي مبنا براي جستجوي پيوسته ميباشد.
از خصوصيات روش‌هاي ابتكاري برگرفته از طبيعت، مي‌توان به موارد زير اشاره كرد:
1- پديده‌اي حقيقي در طبيعت را مدلسازي مي‌كنند.
2- بدون قطع مي‌باشند.
3- اغلب بدون شرط تركيبي همانند (عامل‌هاي متعدد) را معرفي مي‌نمايند.
4- تطبيق‌پذير هستند.
خصوصيات بالا باعث رفتاري معقول در جهت تأمين هوشمندي ميشود. تعريف هوشمندي نيز عبارت است از قدرت حل مسائل مشكل؛ بنابراين هوشمندي به حلمناسب مسائل بهينه‌سازي تركيبي منجر میشود.
برخی الگوریتم های بهینه سازی مهم عبارت انداز:
الگوریتم بهینه سازی ازدحام ذرات
در سال 1995 ابرهارت و کنیدی براي اولین بار PSOبه عنوان یک روش جستجوي غیر قطعی براي بهینه سازي تابعی مطرح گشت این الگوریتم از حرکت دسته جمعیپرندگانی که به دنبال غذا میباشند، الهام گرفته شده است. گروهي از پرندگان در فضايي به صورت تصادفي دنبال غذا ميگردند. تنها يك تكه غذا در فضاي مورد بحث وجود دارد. هيچ يك از پرندگان محل غذا را نميدانند. يكي از بهترين استراتژيها ميتواند دنبال كردن پرندهاي باشد كه كمترين فاصله را تا غذا داشته باشد. ايناستراتژي در واقع جانمايه الگوريتم است. هر راهحل كه به آن يك ذره گفته ميشود،PSO در الگوريتم معادل يك پرنده در الگوريتم حركت جمعي پرندگان ميباشد.هر ذره يك مقدار شايستگي دارد كه توسط يك تابع شايستگي محاسبه ميشود. هر چه ذره در فضاي جستجو به هدف – غذا در مدل حركت پرندگان- نزدیكتر باشد،شايستگي بيشتري دارد. همچنين هر ذره داراي يك سرعت است كه هدايت حركت ذره را بر عهده دارد. هرذره با دنبال كردن ذرات بهينه در حالت فعلي، به حركت خوددر فضاي مساله ادامه ميدهد.
الگوریتم کرم شب تاب
الگوریتم کرم شب تاب به عنوان الگوریتم ذهنی مبتنی بر ازدحام، برای وظایف بهینهسازی محدود، ارائه شده است. در این الگوریتم از رفتار تابشی کرمهای شب تابالهام گرفته شده است. کرمهای شب تاب در طبیعت به طور دسته جمعی زندگی میکنند و همواره کرم کم نورتر به سمت کرم پرنور تر حرکت میکند. این الگوریتم یکرویه تکراری مبتنی بر جمعیت را با عوامل بیشمار (تحت عنوان کرمهای شبتاب) به کار می‌گیرد. به این عوامل امکان داده میشود تا فضای تابع هزینه را به صورتموثرتری نسبت به جستجوی تصادفی توزیع شده، بررسی کنند. تکنیک بهینهسازی هوشمند، مبتنی بر این فرضیه است که راهحل یک مشکل بهینهسازی را، میتوان بهعنوان عاملی (کرم شبتاب) در نظر گرفت که به صورت متناسب با کیفیت آن در یک محیط تابیده میشود. متعاقباً هر کرم شبتاب، همتایان خود را (صرف نظر ازجنسیتشان) جذب میکند که فضای جستجو را به صورت موثرتری بررسی میکند. الگوریتمهای کرم شبتاب نورهای ریتمیک و کوتاه تولید میکنند. الگوی نوری هر کدام از کرمهای شبتاب با یکدیگر متفاوت میباشند. الگوریتمهای کرم شبتاب از این نورها به دو منظور استفاده میکنند. 1- پروسه جذب جفتها 2- جذب شکار. به علاوه این نورها میتوانند به عنوان یک مکانیزم محافظتی برای کرمهای شبتاب باشند.
الگوریتم کلونی مورچگان
بهینهسازی گروه مورچه‌ها یا ACO همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز میتوان مطرح کرد. در این روش(ACo)، مورچه‌های مصنوعی به‌وسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مسئله فراهم نمایند. همچنین در این روش میتوان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.
الگوریتم ژنتیک
الگوریتمهای ژنتیک، تکنیک جستجویی در علم رایانه برای یافتن راهحل تقریبی برای بهینهسازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده میکند. این الگوریتم برای اولین بار توسط جان هنری هالند معرفی شد. در واقع الگوریتمهای ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده میکنند. الگوریتمهای ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. در هوش مصنوعی الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده میکند. مسئله‌ای که باید حل شود دارای ورودی‌هایی می‌باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه‌حلها تبدیل میشود سپس راه حلها بعنوان کاندیداها توسط تابع ارزیاب (Fitness Function) مورد ارزیابی قرار می‌گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می‌یابد. الگوریتم ژنتیک بطور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش‌های آن به صورت فرایندهای تصادفی انتخاب می‌شوند.
منبع
بهينه‌سازی و معرفي روشهای آن قسمت 1
بهينه‌سازی و معرفي روشهای آن قسمت 2
بهينه‌سازی و معرفي روشهای آن قسمت 3
