بهينهسازی مسائل رياضی به روش مورچهها(aco)
تا به حال روش كار بدينگونه بوده است كه زيست شناسان و بيولوژيستها طبيعت را تنها به منظور درك كامل و بهتر آن مطالعه میكردند. هدف تنها درك مكانيزمهای موجود در طبيعت بودهاست. اما اكنون در واقع حاصل كار بيولوژيستها میتواند الهامبخش مهندسان باشد. دست كم در موضوع مورد بحث ما كه حل بهينه(هوشمندانه) مسائل است.
يكی از جالبترين سيستمهای مورد مطالعه تا كنون، كه كاربردهايی هم در مهندسی يافتهاست كولونی مورچههاست. در واقع مورچهها قادر به يافتن كوتاهترين مسير از لانه به منبع غذا هستند. كسانی كه با علوم مهندسی(مشخصاً رباتيك) يا رياضی به صورت اعم سرو كار دارند به خوبی با اين صورت مسئله آشنا هستند و میدانند كه يافتن كوتاهترين مسير يك مسئله بهينهسازيست (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 به اين منظور دارای اين برتری به ساير روشهاست كه بسيار با طبيعت ديناميك شبكه اينترنت سازگار است. زيرا به عنوان مثال ممكن است مسيری كه تا به حال خلوت بوده و كمترين تأخير را داشته ، اكنون به دلايلی شلوغ باشد و يا در مسيری، يك مسيرياب از كار افتاده باشد و ... كه همه اينها به شبكه اينترنت خصلتی پويا همانند خصلت دنيای واقعی مسيريابی مورچهها میدهد. با توجه به آنچه در انتهای بخش قبل گفتهشد ، بعد از از كار افتادن هر مسير همواره بهترين راه حل بعدی توسط اين روش در دسترس است.
رابطه سرعت رشد جانوران با فشار محیط
اگر گونه های زنده پستانداران امروزی را به ترتیب اندازه جثه انها ردیف کنیم مشاهده خواهیم کرد که به ترتیب از جثه های بزرگ ,سرعت رشد پستانداران کمتر می شود.یک موش سرعت رشد بالایی داشته و در عرض چند روز بالغ می شود.فیل که بزرگترین پستاندار خشکی است برای بالغ شدن بیشتر از ده سال زمان لازم دارد.پس هر چه جثه جانور بزرگتر باشد سرعت رشد او کمتر شده و زمان لازم جهت بلوغ جانور طولانی تر است.
بزرگترین جانور زنده امروزی والها هستند که انها نیز متعلق به رده پستانداران می باشند.میدانیم که والها حداقل 20برابر یک فیل جثه دارند,با این حساب باید برای بالغ شدن خود,به یک دوره بسیار طولانی احتیاج داشته باشند.
یعنی در حدود بیست تا سی سال .ولی در طبیعت,انها با سرعت فوق العده ای رشد می کنند و در زمان بسیار کوتاهی بالغ می شوند.یک وال 120تنی با طول 30 متر که 24 برابر یک فیل است تنها در عرض سه سال بالغ می شود.
دلیل رشد سریع والها چیست؟
فیل در خشکی زندگی می کند ولی والها در داخل اب زندگی می کنند.اب از هوا متراکم تر است و فشار داخل اب به مراتب بیشتر از هواست.با هر 10 متر که در داخل اب فرو می رویم,فشار محیط دوبرابر می شود.به این ترتیب محیطی که یک وال در ان زندگی می کند چندین برابر فشار محیطی ست که یک فیل زندگی می کند.
ارتباط فشار محیط و سرعت رشد جانوران:
اگر در ازمایشگاه ,محیط هایی با فشارهای متفاوت ایجاد کنیم و جانوران مشابه را در ان پرورش دهیم می توانیم اختلاف سرعت رشد انها را با هم مقایسه کنیم و بدانیم که ایا با افزایش فشار محیط ,سرعت رشد جانوران بیشتر میشود یا کمتر؟
وقتی در اب دریا به طرف اعماق می رویم در ازای هر 10 متر ,یک اتمسفر بر فشار محیط افزوده می شود.بنابر این در اعماق اب فشار بسیار بالایی حاکم است.با این حساب جانورانی که در اعماق مختلف دریا زندگی میکننددر فشارهای مختلف زندگی می کنند .با مطالعه جانوران در اعماق دریاها مشاهده می شود که سرعت رشد و اندازه جثه جانوران در اعماق دریا ها به مراتب بیشتر و بزرگتر از گونه های مشابه خود در قسمتهای کم عمق در یا می باشند. در اعماق زیاد اب دمای محیط بیش از اندازه سرد است و محیط کاملا تاریک است.بنابر این اثر رشد جانداران بر روی انان و مشاهده ان به مراتب سخت تر است.
حتی در زمان دایناسورها اگر معتقد باشیم که سرعت رشدشان بالا و مدت زمان بلوغ انان کوتاه بوده می توانیم فشار بالای محیط را در ان زمان دخیل بدانیم.ممکن است این تصور باشد که در جاذبه کم ان زمان,فشار هوا هم باید کمتر بوده باشد نه بیشتر!اما فشار هوااعلاوه بر مقدار جاذبه سیاره به عوامل دیگری نیز مربوط است.مثلا در سیاره زهره که جاذبه در سطح ان کمتر از کره زمین است ,فشار اتمسفر در سطح ان حدود سی برابر فشار اتمسفر کره زمین است و این امر به دلیل وجود گاز کربنیک زیاد در اتمسفر ان سیاره است.بنابر این با افزایش فشار محیط ,سرعت رشد جانوران نیز بالا میرود. بررسی های فوق در علم جانور شناسی مورد بحث است .تا بعد...
.................................................. .................................................. ...................
لاكپشتها
لاکپشتها هرگز پیر نمی شوند .انها بر خلاف انسانها از لحاظ زیستی هرگز به بلوغ کامل نمی رسند .لاکپشتها به عنوان موجوداتی شناخته شده اند که بیشتر از 150 سال عمر میکنند بدون انکه کوچکترین علامتهای پیری و فرسودگی را نشان دهند.انها بیشتر به دلیل صدمه دیدن,بیماری و یا شکار سایر موجودات از بین می روند.
زندگی خارقالعاده پشهها!
ایسکانیوز – دانشمندان موفق به کشف زندگی خارقالعاده پشهها شدند.
به گزارش سرویس علمی پژوهشی ایسکانیوز به نقل از نشریه science، حشرات موجوداتی کوچک و از گروه دوبالان هستند گونههایی از مگسهای ماده قبل ازتخمگذاری بایدحداقل یکبار از خون پستانداران بمکند. مگسهای نر دارای سه لوله تغذیه هستند اما آنها توانایی نیش زدن ندارند آنها از میوهها و شیره گیاهان تغذیه میکنند. جنس ماده آنها از ویژگیهای خاصی برخوردارند مثلا دارای صدایی هستند که درمیان پوستههای سخت درختان ارتعاش پیدا میکند تخم آنها یا تکتک هستند یا به هم چسبیدهاند آنها معمولا در آبهای راکد، حوضها، استخرها، محفضههای باز و محلهای وابسته به آبزیان زندگی میکنند نوع ویژهای از محل سکونت آنها به انواع گونههای آنها بستگی دارد مثلا نوع Larvae وابسته به آب هستند از حیوانات و گیاهان میکروسکوپی تغذیه میکنند. دستهای دیگر از پشه به نام پشه آنوفل (مالاریا) درداخل یک لوله هوا رشد و نمو میکنند. یکی از روشهای کنترل افزایش پشهها شناور کردن ماده روغنی بر روی آب است که ازتنفس آنها جلوگیری میکند و باعث مرگ آنها میشود. تعداد زیادی از پشههای آنوفل به وسیله محل استقرار راکد آنها قابل تشخیص هستند نوع دیگری از پشههای ویروس تب زرد را منتقل میکند حشراتی مانند سنجاقک و چندین حشره دیگر آبزی را میخورند.