الگوریتم مورچگان
مفاهیم اولیه الگوریتم مورچگان :
تاریخچه :الگوريتم کلونی مورچه براي اولين بار در سال 1992 توسط دوريگو و همکارانش به عنوان يک راه حل چند عامله برای مسائل مشکل بهينه سازی مثل فروشنده دوره گرد ارائه شد.مقدمه :هنگامی که یک مورچه به شکل تصادفی تنها حرکت می کند و به یه دوراهی می رسد به احتمال زیاد مسیری را انتخاب می کند که دارای بوی فرومون بیشتر است و آن مسیر را ادامه می دهد . همچنین با فرمونی که از خود ترشح می کند احتمال انتخاب آن مسیر را برای سایر مورچگان افزایش میدهد .یکی از جالبترین رفتار های مورچه ها رفتاری است که برای پیدا کردن غذا از خود نشان می دهند . ، بویژه رفتاری که برای پیدا کردن کوتاهترین و بهترین مسیر میان آشیانه ( لانه ) و منبع غذا از خود بروز می دهند .آنچه بنيان فكری الگوريتم مورچگان بر آن بنا شده است را می توان بسادگی و در يك جمله بيان نمود: " مورچه ها در بين موانع و محدوديت های موجود در طبيعت هميشه از بين جايگشت های متفاوت برای رسيدن به غذا، بهينه ترين راه را انتخاب می كنند".عامل هوشند : موجودی است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روی محيط تاثير بگذارد. درباره ی مورچگان طبیعی : 1 - فرومون : (Pheromone) مورچه ها هنگام راه رفتن از خود ردی از ماده شيميايی فرومون جای می گذارند البته اين ماده بزودی تبخير می شود ولی در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقی مي ماند.2 - هوشمندی توده ای : یک توده (Swarm) عبارت است از مجموعه ای از عامل ها که با یکدیگر به صورت مستقیم (کلمات ، سیگنال ، علايم و . . .) یا به صورت غیر مستقیم (از طریق تاثیر گذاری در محیط) در تماس هستند و همگی یک مسئله را به شکل گسترده حل می کنند .یکی از خصلت های کلونی مورچه ها هوشمندی توده ای است ، به این معنی که کلونی مورچه ها نه بر اساس هوشمندی یک مغر مرکزی بلکه بر اساس توده ای از عامل های هوشمند و رابطه ی بین آنها عمل می کنند .3 - اجتماعی بودن :مورچه ها موجودات اجتماعی هستند و رفتار آنها در جهت بقای کلونی است تا در بقای جزء و همچنین دارای کار گروهی و تقسیم کار هستند .4 - تصمیم گیری :آنها برای انتخاب بین دو مسیر به صورت احتمالی (statistical) تصمیم میگیرند و معمولا مسیری را انتخاب می کنند که دارای فرومون بیشتری است (قبلا مورچه های بیشتری از آن عبور کرده است) .الگوریتم کلونی مورچگان : مورچه ها هنگام انتخاب بين دو مسير بصورت احتمالاتی مسيری را انتخاب می کنند که فرومون بيشتری داشته باشد يا بعبارت ديگر مورچه های بيشتری قبلا از آن عبور کرده باشند. حال می بینیم که همين تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد : همانطور که در شکل می بينيم ...
پاور پوینت آموزش الگوریتم مورچگان(ACO)
پاور پوینت آموزش الگوریتم مورچگان(ACO) ارائه شده توسط فرزاد فرزام راد مقطع کارشناسی ارشد مهندسی صنایع دانشگاه آزاد اسلامی واحد بناب لینک دانلود مستقیم
الگوريتم مورچگان چیست؟ توضیح با یک مثال ساده
توسعه اين الگوريتم از رفتار مورچه‌ها الهام گرفته است. مورچه‌ها حشرات اجتماعي هستند. آنها در دسته بزرگي(Colony) از جمعيت زندگي مي كنند و رفتارشان تابع بقاي كولوني است نسبت به بقاي فردي. از رفتار مورچه‌هاي كارگر كه براي يافتن غذا تلاش مي‌كنند در الگوريتم مورچگان الهام گرفته شده است، اينكه مورچه چگونه كوتاه‌ترين مسير را براي يافتن غذا تا لانه طي مي‌كند. براي يافتن غذا، مورچه ها ابتدا محدوده دور لانه را بطور تصادفي طي مي‌كنند. در حال حركت، مورچه‌ها اثري از خود به نام فرومون(pheromone) روي زمين به جا مي‌گذارند. مورچه‌ها فرومون را مي‌توانند بو بكشند، در هنگام انتخاب مسير، مسيري كه اثر فرومون قوي‌تري دارد، احتمال انتخاب بيشتري خواهد داشت. به محض اينكه مورچه‌اي منبع غذايي پيدا كرد، كيفيت و مقدار غذا را ارزيابي مي‌كند و مقداري از غذا را با خود به لانه مي‌برد. در طول بازگشت، اثر فرومون به جاي مانده در زمين بستگي به كيفيت و كميت غذاي حمل شده دارد. اثر فرومون ، ساير مورچه ها را در رسيدن به منبع غذا راهنمايي مي‌كند. با توجه به اينكه فرومون در اثر مجاورت با هوا تبخير مي‌شود، از مسيري كه مورچه كمتري عبور كند يعني در اثر تشديد نشدن، فرومون بعد از مدتي كاملاً محو مي‌شود. در واحد زماني يكسان، از مسيرِكوتاه‌تر نسبت به مسير طولاني‌تر مورچه‌هاي بيشتري عبور مي‌كنند پس فرومون بيشتري باقي مي‌ماند. در نتيجه‌ي گذشت زمان پس از مدتي از مسيري كه مورچه نگذشته هيچ اثري از فرومون نخواهد ماند و همه از مسير كوتاه‌تر عبور مي‌كنند(Deneubourg et. al 1990; Grassé 1959). جزئيات بيشتر اين عمل توسط دنبرگ و ديگران(Deneubourg et. al) (1990)آورده شده است كه آنها را قادر مي‌سازد كوتاه ترين مسير را از لانه تا دانه بپيمايند.شكل(1) را ببينيد.شكل (1) حركت مورچه‌ها براي رسيدن به غذا. اين مثال چگونگي حركت مورچه‌ها براي رسيدن به كوتاه‌ترين مسيرشان را نشان مي‌دهد. در اينجا تنها دو راه براي رسيدن به غذا وجود دارد. مورچه‌ها با كمكِ فروموني كه از بدنشان ترشح مي‌شود كوتاه‌ترين مسير را پيدا مي‌كنند بدين ترتيب در سمتي كه فرومون بيشتري باشد احتمال گام نهادن در آن مسير بيشتر مي‌شود(Tfaili & Siarry 2007) 2. سيستم مورچه‌ها براي مسأله فروشنده دوره گرد: اولين الگوريتم مورچگان به عنوان يك مثال در اينجا اولين الگوريتم مورچگان ارائه مي‌شود كه سيستم مورچه‌ها(Ant System (AS)) ناميده مي‌شود در كاربرد همين موضوع است كه چنين آمده(Dorigo 1992; Dorigo, Maniezzo and Colorni 1996) تعريف :مسأله فروشنده دوره گرد بصورت گرافي نمايش داده مي‌شود كه گره‌ها شهر ها و يال‌ها مسير هاي موجود بين اين شهر‌ها ...
انواع مختلف الگوریتم بهینه سازی مورچگان
انواع مختلف الگوریتم بهینه سازی مورچگان در پایین تعدادی از انواع شناخته شده از الگوریتم بهینه سازی مورچگان را معرفی می‌کنیم: ۱- سیستم مورچه نخبگان: در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد می‌کند. همچنین این روش برای تمام مورچه‌های مصنوعی باید انجام شود. ۲- سیستم مورچه ماکسیموم – مینیمم: یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد می‌کند و تمام گره‌های مجاور ان به مقدار فرمون بیشینه به مقدار دهی اولیه می‌شوند. ۳- سیستم کلونی مورچه: که در بالا توضیحات کافی داده شده است. ۴- سیستم مورچه بر اساس رتبه: تمام راه حل‌های بدست آماده بر اساس طول جواب رتبه بندی می‌شوند و بر اساس همین رتبه بندی مقدار فرمون آزاد سازی شده توسط آنها مشخص خواهد شد و راه حل با طول کمتر از راه حل دیگر با طول بیشتر مقدار فرمون بیشتری آزاد می‌کند. ۵ - سیستم مورچه متعامد مداوم: در این روش مکانیزم تولید فرمون به مورچه اجازه میدهد تا برای رسیدن به جواب بهتر و مشترک با بقیه مورچه‌ها جستجو انجام دهد با استفاده از روش طراحی متعامد مورچه می‌تواند در دامنه تعریف شده خود به صورت مداوم برای بدست آوردن بهترین جواب جستجو کند که این عمل به هدف رسیدن به جواب بهینه و صحیح ما را نزدیک می‌کند. روش طراحی متعامد می‌تواند به دیگر روش‌های جستجو دیگر گسترش پیدا کنند تا به مزیت‌های این روش‌های جستجو اضافه کند.
الگوریتم AS از کلونی مورچگان :
الگوریتم AS : AS مخفف Ant System است که دریگو ایده ساده فرومون بیشتر روی مسیر کوتاهتر و غذای بیشتر را برای یافتن راه حل های مناسب در مسائل بهینه سازی ، سخت مورد استفاده قرار داد و این روش را بعنوان اولین نسخه از الگوریتم ACO ارائه کرد .در این الگوریتم وظیفه ی اصلی هر مورچه مصنوعی یافتن کوتاه ترین بین یک جفت گره در یک گراف است .قانون تصمیم گیری برای مورچه k در گره i ، که می خواهد یکی از گره ها را از بین گره های ملاقات نشده Ni انتخاب کند از فرمول زیر ( احتمال ) بدست می آید : : نشان دهنده ی مقدار فرومون روی یال (i,j) است . : نشان دهنده ی مقدار فاصله ی بین دو گره ی i,j است . : توان هایی هستند که با تغییر آنها میزان اهمیت هر یک را نسبت به دیگری می توان تغییر داد.همچنین مورچه ها در حالی که از یک گره i به گره j می روند اطلاعات فرومون که روی یال (i,j) میریزند از فرمول زیر بدست می آید : : فرومونی که مورچه هنگام عبور روی یال i,j می ریزد .فرمول تبخیر فرومون برای اجتناب از همگرایی سریع همه ی مورچه ها به شکل زیر است : که در این فرمول غلظت فرومون به طور خودکار و در هر بار تکرار به مقدار p کاهش می یابد .
دانلود چند کتاب مربوط به الگوریتمهای فرا ابتکاری
1- دانلود کتاب An introduction to genetic Algorithms for scientists and engineers 2- دانلود کتاب ANT COLONY OPTIMIZATION METHODS AND APPLICATIONS 3- دانلود کتاب Ant Colony Optimization 4- دانلود کتاب Artificial Neural Networks and Information Theory 5- دانلود کتاب ARTIFICIAL NEURAL NETWORKS 6- دانلود کتاب Local Search Techniques Focus on Tabu Search 7- دانلود کتاب Simulated Annealing Theory with Applications
فیلم آموزشی جامع الگوریتم مورچگان کلاسیک یا ACO در متلب
بهینه سازی کلونی مورچه ها یا Ant Colony Optimization و (به اختصار ACO)، که در سال 1992 توسط مارکو دوریگو (Marco Dorigo) و در رساله دکتری وی مطرح شد، یکی از بارزترین نمونه ها برای روش های هوش جمعی است. این الگوریتم از روی رفتار جمعی مورچه ها الهام گرفته شده است. مورچه ها با همکاری یکدیگر، کوتاه ترین مسیر را میان لانه و منابع غذایی پیدا می کنند تا بتوانند در کمترین زمان مواد غذایی را به لانه منتقل کنند. هیچ کدام از مورچه ها، به تنهایی قادر به انجام چنین کاری نیستند، اما با همکاری و پیروی از چند اصل ساده، بهترین راه را پیدا می کنند. الگوریتم مورچه ها، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندان بالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند. به عنوان مثال، عملکرد مورچه های آرژانتینی در یافتن کوتاه ترین مسیر بین لانه و منبع غذایی، بسیار عجیب و حیرت انگیز است. مورچه آرژانتینی عملا کور است و طبعا کوتاه ترین مسیر برای او مفهومی ندارد و توسط او قابل شناخت نمی باشد. اما با وجود چنین کمبودی، توده ای از این مورچه ها می توانند با همکاری یکدیگر، کوتاه ترین مسیر موجود بین لانه و محل مواد غذایی را پیدا کنند. الگوریتم های دیگری نیز بر اساس الگوریتم مورچه ها ساخته شده اند که همگی سیستم های چند عاملی هستند و عامل ها مورچه های مصنوعی یا به اختصار مورچه هایی هستند که مشابه با مورچه های واقعی رفتار می کنند. این الگوریتم برای حل و بررسی محدوده وسیعی از مسائل بهینه سازی به کار برده شده است. از این میان می توان به حل مسأله کلاسیک فروشنده دوره گرد و همچنین مسأله راهیابی در شبکه های مخابرات راه دور اشاره نمود. فیلم آموزشی جامع الگوریتم مورچگان در متلب، شامل مباحث تئوری و عملی در خصوص بهینه سازی کلونی مورچگان یا ACO است و می تواند به عنوان یک مرجع بسیار کامل، برای استفاده دانشجویان و دانش پژوهان مورد استفاده قرار بگیرد. مطالب و مباحث این فیلم آموزشی به زبان فارسی روان، و توسط مهندس سید مصطفی کلامی هریس ارائه شده است. سرفصل های مهم مورد بحث در این فیلم آموزشی عبارتند از: مروری بر مبانی و مفاهیم اساسی هوش جمعی (Swarm Intelligence) مبانی تئوری الگوریتم مورچگان یا ACO تشریح بخش های مختلف الگوریتم مورچگان بررسی انواع نسخه های الگوریتم مورچگان پیاده سازی الگوریتم مورچگان در متلب بیان ریاضی مسأله فروشنده دوره گرد یا TSP پیاده سازی گام به گام الگوریتم مورچگان در محیط متلب برای حل مسأله فروشنده دوره گرد نمایش نتایج حاصل از حل مسأله TSP به صورت گرافیکی جمع بندی و نتیجه گیری های نهایی توجه: این فیلم ...
کد متلب الگوریتم مورچگان برای مسأله فروشنده دوره گرد
MATLAB Code Ant Colony Optimization for Traveling Salesman Problem - ACO TSP MATLAB M file Ant Colony Optimization for Traveling Salesman Problem - ACO TSP کد متلب الگوریتم مورچگان برای مسأله فروشنده دوره گردبرای دانلود اینجا را کلیک کنید.
کتاب تحقیق در عملیات یا پزوهش عملیاتی با عنوان Introduction to Operations Research
دانلود کتاب Introduction to Operations Research اثر لیبرمن و هیلر Introduction to Operations ResearchSeventh Edition | Hillier/Lieberman دانلود
الگوریتم مورچگان
سلام به همه دوستان. پيدا كردن مسير درست رسيدن به قله آرزو ها گاهي چقدر دشوار و سخت ميشه!!!كاشكي مسير خيلي واضح مي بود تا فقط سختي پيمودنش باشه.اينكه گاهي واسه ادامه راه چندتا مسیر پيدا ميشه به نظرم خيلي بده آخه كدوميك از مسير هاست كه راحتتره و هم نزديكتر!!!حداقل كاشكي مثل مورچه ها ميتونستيم راه بقيه رو بريم.ولي حيف!آخه ما انسانها به نظرم نميتونيم زندگيمون رو از ديگران تقليد كنيم چونكه واسه هر كدوم از ما اتفاقاتي ميفته كه حتي اگه شبيه به زندگي بقيه باشه در شرايط مكاني و زماني خاص خودش رخ ميده و نيازبه يك تصميم مخصوص به خودش داره! من از امروز تصميم گرفتم مثل يه داوطلب كنكور ارشد درس بخونم!!تا شاید آزاد قبول شم آخه من واسه ارشدسراسري به خاطر يه سري از مشكلات نتونستم درس بخونم.... ايشالله قبولي همه دوستان در تمامي كنكور هاي زندگيشون..... روز آفتابی سرد زمستونی همگي قشنگ وزيبا