ravegoat
19-06-12, 10:35
بهينه سازي با كلوني مورچه ها (Ant Colony Optimization يا ACO) شاخه اي از علم هوش دسته جمعي (Swarm Intelligence يا SI) است كه با ايده گرفتن از رفتار دسته جمعي مورچه ها در كلوني، به حل مسايل بهينه سازي در دنياي واقعي مي پردازد.
مشاهده شده كه مورچه ها همواره مسيري را از لانه به سمت غذا دنبال مي كنند كه كوتاه ترين مسير بين لانه و غذا خواهد بود. اما چگونه مورچه ها اين مسير را تشخيص مي دهند؟
تحقيقات نشان مي دهد مورچه ها در ابتدا نمي دانند كوتاه ترين مسير بين غذا و لانه كجاست! در نتيجه هر مورچه يك مسير تصادفي را انتخاب مي كند تا به غذا برسد. هر مورچه در هر مسيري كه حركت كند، هورموني از خود ترشح مي كند و بر راه خود بر جاي مي گذارد و بدين شكل مسير حركت آن مورچه مشخص مي گردد. هر مورچه اي كه زود تر غذا را بيابد در واقع مسير كوتاه تري را طي كرده است و در نتيجه زود تر نيز به لانه باز مي گردد. به علاوه اين مورچه هورمون بيش تري روي مسير خود براي جاي گذاشته است، زيرا مسير را رفته و برگشته است در نتيجه دوز هورمون مسير او دو برابر دوز هورمون مسير هايي خواهد بود كه مورچه هاي ديگر انتخاب كرده اند ولي به دليل طولاني بودن، هنوز نتوانسته اند برگردند.
در ادامه اگر مورچه ي ديگري بخواهد به سوي غذا حركت كند، احتمال آن كه مسيري با دوز هورمون بالا تر را انتخاب كند، بيش تر خواهد بود. اگر چنين شود، آن مورچه هم در كم ترين زمان مسير رفت و برگشت را مي پيمايد و دوز هورمون اين مسير را بالا مي برد در حالي كه ممكن است همچنان مورچه هاي مسير هاي ديگر حتي به غذا نيز نرسيده باشند و درنتيجه دوز هورمون مسيرشان مقدار پاييني خواهد بود. اگر همين روند ادامه يابد، دوز هورمون كوتاه ترين مسير بيش تر و بيش تر مي شود و به جايي خواهد رسيد كه احتمال انتخاب آن از سوي مورچه هاي جديد آن چنان بالا خواهد بود كه در نهايت تمام مورچه ها همين مسير را براي رسيدن به غذا انتخاب مي كنند. بدين شكل مورچه ها كوتاه ترين مسير بين غذا و لانه را يافته اند.
6964
جالب آن است كه اگر مكان غذا تغيير يابد، مورچه پس از مدتي مسير قبلي را رها كرده و مسير بهينه ي جديد را پيدا مي كنند. اين امر به خاطر آن است كه هورمون هاي به جا مانده پس از مدتي تبخير مي شوند و بدين شكل دوز هورمون هر مسير كاهش مي يابد و اگر آن مسير ديگر بهينه نباشد، كاهش دوز هورمون آن را ديگر مورچه اي با ترشح هورمون جبران نمي كند و در نهايت احتمال انتخاب مسير به حداقل مي رسد. اين ويژگي در حل مسايل ديناميكي مانند Network Routing بسيار كمك كننده است.
الگوريتم هاي مختلفي جهت مدل سازي رياضي رفتار فوق وجود دارند؛ مانند:
Ant System
Min-Max Ant System
Ant Colony System
كه هريك براي حل مسئله اي خاص، مزايا و معايبي دارند. مقاله ي پيوست شده ضمن تشريح دو الگوريتم اول، نتايج آن دو را در حل مسئله ي فروشنده ي دوره گرد (TSP) مقايسه كرده است.
مشاهده شده كه مورچه ها همواره مسيري را از لانه به سمت غذا دنبال مي كنند كه كوتاه ترين مسير بين لانه و غذا خواهد بود. اما چگونه مورچه ها اين مسير را تشخيص مي دهند؟
تحقيقات نشان مي دهد مورچه ها در ابتدا نمي دانند كوتاه ترين مسير بين غذا و لانه كجاست! در نتيجه هر مورچه يك مسير تصادفي را انتخاب مي كند تا به غذا برسد. هر مورچه در هر مسيري كه حركت كند، هورموني از خود ترشح مي كند و بر راه خود بر جاي مي گذارد و بدين شكل مسير حركت آن مورچه مشخص مي گردد. هر مورچه اي كه زود تر غذا را بيابد در واقع مسير كوتاه تري را طي كرده است و در نتيجه زود تر نيز به لانه باز مي گردد. به علاوه اين مورچه هورمون بيش تري روي مسير خود براي جاي گذاشته است، زيرا مسير را رفته و برگشته است در نتيجه دوز هورمون مسير او دو برابر دوز هورمون مسير هايي خواهد بود كه مورچه هاي ديگر انتخاب كرده اند ولي به دليل طولاني بودن، هنوز نتوانسته اند برگردند.
در ادامه اگر مورچه ي ديگري بخواهد به سوي غذا حركت كند، احتمال آن كه مسيري با دوز هورمون بالا تر را انتخاب كند، بيش تر خواهد بود. اگر چنين شود، آن مورچه هم در كم ترين زمان مسير رفت و برگشت را مي پيمايد و دوز هورمون اين مسير را بالا مي برد در حالي كه ممكن است همچنان مورچه هاي مسير هاي ديگر حتي به غذا نيز نرسيده باشند و درنتيجه دوز هورمون مسيرشان مقدار پاييني خواهد بود. اگر همين روند ادامه يابد، دوز هورمون كوتاه ترين مسير بيش تر و بيش تر مي شود و به جايي خواهد رسيد كه احتمال انتخاب آن از سوي مورچه هاي جديد آن چنان بالا خواهد بود كه در نهايت تمام مورچه ها همين مسير را براي رسيدن به غذا انتخاب مي كنند. بدين شكل مورچه ها كوتاه ترين مسير بين غذا و لانه را يافته اند.
6964
جالب آن است كه اگر مكان غذا تغيير يابد، مورچه پس از مدتي مسير قبلي را رها كرده و مسير بهينه ي جديد را پيدا مي كنند. اين امر به خاطر آن است كه هورمون هاي به جا مانده پس از مدتي تبخير مي شوند و بدين شكل دوز هورمون هر مسير كاهش مي يابد و اگر آن مسير ديگر بهينه نباشد، كاهش دوز هورمون آن را ديگر مورچه اي با ترشح هورمون جبران نمي كند و در نهايت احتمال انتخاب مسير به حداقل مي رسد. اين ويژگي در حل مسايل ديناميكي مانند Network Routing بسيار كمك كننده است.
الگوريتم هاي مختلفي جهت مدل سازي رياضي رفتار فوق وجود دارند؛ مانند:
Ant System
Min-Max Ant System
Ant Colony System
كه هريك براي حل مسئله اي خاص، مزايا و معايبي دارند. مقاله ي پيوست شده ضمن تشريح دو الگوريتم اول، نتايج آن دو را در حل مسئله ي فروشنده ي دوره گرد (TSP) مقايسه كرده است.