تا به حال روش كار بدينگونه بوده است كه زيست شناسان و بيولوژيستها طبيعت را تنها به منظور درك كامل و بهتر آن مطالعه میكردند. هدف تنها درك مكانيزمهای موجود در طبيعت بودهاست. اما اكنون در واقع حاصل كار بيولوژيستها میتواند الهامبخش مهندسان باشد. دست كم در موضوع مورد بحث ما كه حل بهينه(هوشمندانه) مسائل است.
يكی از جالبترين سيستمهای مورد مطالعه تا كنون، كه كاربردهايی هم در مهندسی يافتهاست كولونی مورچههاست. در واقع مورچهها قادر به يافتن كوتاهترين مسير از لانه به منبع غذا هستند. كسانی كه با علوم مهندسی(مشخصاً رباتيك) يا رياضی به صورت اعم سرو كار دارند به خوبی با اين صورت مسئله آشنا هستند و میدانند كه يافتن كوتاهترين مسير يك مسئله بهينهسازيست (Optimization) كه گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بنابراين اين سؤال برای دانشمندان مطرح شد كه مورچهها چگونه اين مسئله را حلكردهاند؟
در واقع راهحل مورچهها كه يك راهحل تودهایاست بسيار ساده است. مورچهها هنگام راه رفتن از خود ردی از فرمون (pheromone) به جا میگذارند. البته اين فرمون به زودی تبخير میشود اما در كوتاهمدت به عنوان رد مورچه بر سطح زمين باقی میماند. يك رفتار بسيار ساده پايهای در مورچهها وجود دارد: آنها هنگام انتخاب بين دو مسير به صورت احتمالاتی(Statistical) مسيری را انتخاب میكنند كه فرمون بيشتری داشته باشد يا به عبارت ديگر مورچههای بيشتری قبلا از آن عبور كردهباشند. حال دقت كنيد كه همين يك تمهيد ساده چگونه منجر به پيدا كردن كوتاهترين مسير خواهد شد:
فرض كنيد در مسير شكل 1 يك مانع قرارگرفته و مورچههای ديگر به سادگی قادر به دستيابی به منبع غذا نباشند. همانگونه كه مشخص است اينك دو راه برای دستيابی به غذا وجود دارد راه بالا كه كوتاهتر و راه پايين كه طولانیتر است.حال مورچهها بر اساس همان رفتار پايهای كه گفتيم به تصادف يكی از دو راه بالا يا پايين را انتخاب میكنند. فرض كنيد نيمی از راه بالايی و نيمی از راه پايين حركت كنند و البته در دو جهت يعنی هم به سمت منبع غذا و هم به سمت لانه.
در ابتدا انتخاب كاملاً تصادفيست اما بعد ازاينكه در هر يك از مسيرها ردی از فرمون ايجادشد مورچهها به احتمال بيشتر مسير پر فرمونتر را انتخاب میكنند. از آنجايی كه طول مسير بالا كوتاهتر است زمان رفت و برگشت به آن هم كمتر است پس مورچههای بيشتری نسبت به مسير پايين آن را طی میكنند. بنابراين فرمون بيشتری در آن ترشح میشود و در نهايت با احتمال بيشتری توسط مورچهها انتخاب میشود(هر چه فرمون بيشتر باشد احتمال انتخاب مسير بيشتر است). به همين دليل پس از مدتی همه مورچهها(يا تقريباً همه مورچهها) مسير كوتاهتر را طی خواهندكرد.
بايد توجه كرد كه هرچند احتمال انتخاب مسير پر فرمونتر توسط مورچهها بيشتر است اما اين كماكان احتمال است و قطعيت نيست. به عبارتی اگر مسير A پرفرمونتر از مسير B باشد بههيچوجه نمیتوان نتيجهگرفت كه همه مورچهها از مسير A حركت خواهندكرد بلكه تنها میتوان گفت كه مثلاً به احتمال 90% هر مورچه مسير A را انتخاب خواهد كرد.
اگر به جای اين احتمال قطعيت بود، يعنی اگر هر مورچه حتماً و حتماً مسير پر فرمونتر را انتخاب میكرد ، اساساً روش ممكن بود به جواب نرسد. فرض كنيد تصادفاً اولين مورچه مسير پايين را انتخاب میكرد و ردی از فرمون در آن به جا میگذاشت. در اينصورت همه مورچهها به قطعيت رد او را دنبال میكردند و هيچوقت مسير كوتاهتر را پيدا نمیكردند. بنابراين تصادف نقش عمدهای در ACO بر عهده دارد(و البته در هوشمندی تودهای).
نكته ديگری كه بايد در نظر داشت مسئله تبخير و از بين رفتن فرمون يا رد مورچههاست(Evaporation). فرض كنيد كه مانع موجود در شكل برداشته شود. اگر فرمونها تبخير نشوند ، مورچهها اساساً همان مسير پر فرمون قبلی را دنبال میكنند و به حالت اوليه(شكل 1) كه كوتاهترين مسير بود باز نمیگردند. ولی با در نظر گرفتن مسئله تبخير فرمون، بعد از برداشتن مانع، پس از چندی مورچهها بازهم كوتاهترين مسير را پيدا خواهندكرد.
(Ant Colony Optimization)ACO و (Traveling Sales Man)TSP: استفاده از بهينهسازی كولونی مورچهها در مسئله فروشنده دورهگرد
يكی از مسائل كلاسيك تئوری گراف در رياضيات مسئله فروشنده دورهگرد است كه البته كاربردهای بسيار زيادی در علوم مهندسی دارد. صورت مسئله ازاين قرار است. يك فروشنده دوره گرد میخواهد از شهر خودش شروع به حركت كرده و پس از گذر از N شهر به شهر خود بازگردد. منتها شرط ايناست كه اولاً از هر شهر فقط يك بار عبور كند و دوماً كوتاهترين مسير را در مجموع طی كند. در واقع مسئله يافتن كوتاهترين مسيريست كه N گره يك گراف را به هم متصل میكند.
برای اين مسئله تاكنون راه حلهای زيادی ارائه شده است كه اكنون میتوان گفت روش ACO در ليست بهترين اين راه حلها میباشد. برای استفاده از ACO در TSP میتوان متا الگوريتم زير را پيشنهاد داد:
تعداد زيادی عامل هوشمند در نظر میگيريم كه قرار است از N نود يك گراف(N شهر) عبور كنند. اين عاملهای هوشمند شهر بعدی را به تناسب ميزان فرمون موجود در مسير انتخاب میكنند(با در نظر گرفتن عامل تصادف). اين فرمون در كامپيوتر مثلاً میتواند توسط يك عدد يا وزن به هر يال گراف(هر جاده) اختصاص يابد. مثلا مسير شهر A به شهر B دارای وزن 7/0 است، به اين معنی كه ميزان فرمون موجود در مسير 7/0 است.
هر عامل هوشمند پس از طی يك تور كامل در تمامی N شهر به نسبت عكس طول مسير طی شده بر تمامی يالهايی(جادههايی) كه ازآن عبور كرده است فرمون به جا میگذارد. به اين ترتيب پس از مدتی از اجرای الگوريتم همانند كولونی مورچهها تقريباً تمامی عاملهای هوشمند ما كوتاهترين تور بين N شهر را طی خواهندكرد. يعنی كوتاهترين مسير ، مسيريست با بيشترين وزن يا بيشترين فرمون.
بدين ترتيب برای يك مسئله پيچيده رياضی يك راه حل Meta Heuristic ساده يافتهايم كه در زمان نسبتاً معقولی نيز به جواب میرسد.
علاوه بر همه اينها ACO بر ساير روشها يك مزيت مهم ديگر نيز دارد. بقيه روشها فقط كوتاهترين مسير را میيابند و اگر يكی از جادهها يا يالها حذفشود مسئله بايد از ابتدا حل شود. اما در ACO بعد از حذف يك يال میتوان به سادگی مسيری را پيدا كرد كه نسبت به مسير قبلی فرمون كمتر و نسبت به مابقی مسيرها فرمون بيشتری دارد و به اين ترتيب نيازی به حل مجدد مسئله نيست.
بهينهسازی شبكههای كامپيوتری با الهام از كولونی مورچهها
از جمله مسائل مهم ديگری كه ايده AS(Ant System)میتواند در آنها مورد استفاده قرار گيرد مسئله مسيريابی در شبكههای كامپيوتری Routing است.
يكی از خصلتهای مهم كولونی مورچهها هوشمندی تودهایاست كه در ابتدای مقاله به آن اشاره كرديم، بدين معنی كه كولونی مورچهها نه بر اساس هوشمندی يك مغز مركزی بلكه بر اساس تودهای از عاملهای هوشمند (در اينجا مورچهها كه البته هوشمندی بسيار اندكی دارند)، و رابطه بين آنها، عمل میكند. همين ويژگی سبب میشود كه بتوان از اين ايده در بهينهسازی عمل مسيريابی Routing در شبكههای كامپيوتری سود جست.
اطلاعات بر روی شبكه اينترنت به صورت بستههای اطلاعاتی كوچك (Packet) منتقل میشود. هر يك از اين بستهها در طی مسير از مبدأ تا مقصد بايد از گرههای زيادی كه همان مسيريابها (Router ) باشند عبور كند. در داخل هر مسيرياب جدولی قرار دارد كه بهترين مسير بعدی را تا مقصد میتوان از طريق آن شناسايی كرد. بنابراين بستههای اطلاعاتی حين گذر از مسيريابهای مابين راه با توجه به محتويات اين جداول عبور داده میشوند.
روشی به نام ACR(Ant Colony Routing) پيشنهاد شده كه بر اساس ايده كولونی مورچهها به بهينهسازی اين جداول مسير يابی میپردازد و در واقع به هر مسيری با توجه به بهينگی آن امتياز میدهد. استفاده از ACR به اين منظور دارای اين برتری به ساير روشهاست كه بسيار با طبيعت ديناميك شبكه اينترنت سازگار است. زيرا به عنوان مثال ممكن است مسيری كه تا به حال خلوت بوده و كمترين تأخير را داشته ، اكنون به دلايلی شلوغ باشد و يا در مسيری، يك مسيرياب از كار افتاده باشد و ... كه همه اينها به شبكه اينترنت خصلتی پويا همانند خصلت دنيای واقعی مسيريابی مورچهها میدهد. با توجه به آنچه در انتهای بخش قبل گفتهشد ، بعد از از كار افتادن هر مسير همواره بهترين راه حل بعدی توسط اين روش در دسترس است.