پیشینه تحقیق الگوریتم های فرا ابتکاری و روش های حل مسائل بهینه سازی  دارای ۲۹ صفحه می باشد فایل پیشینه تحقیق به صورت ورد  word و قابل ویرایش می باشد. بلافاصله بعد از پرداخت و خرید لینک دنلود فایل نمایش داده می شود و قادر خواهید بود  آن را دانلود و دریافت نمایید . ضمناً لینک دانلود فایل همان لحظه به آدرس ایمیل ثبت شده شما ارسال می گردد.

فهرست مطالب

فصل اول: الگوریتم های فرا ابتکاری    ۴
۱-۱-  مقدمه    ۴
۲-۱-  مرور ادبیات الگوریتم های فرا ابتکاری    ۴
۳-۱-  جمع بندی    ۱۳
فصل دوم:روش های بهینه سازی    ۱۴
۲-۱-  مقدمه    ۱۴
۲-۲-  مسائل بهینه سازی    ۱۴
۲-۳-  بررسی روشهای جستجو و بهینهسازی    ۱۵
۲-۳-۱-   روشهای شمارشی    ۱۶
۲-۳-۲-  روشهای محاسباتی    ۱۷
۲-۳-۳-  روشهای ابتکاری و فرا ابتکاری (جستجوی تصادفی)    ۱۸
۲-۴-   مسائل بهینهسازی ترکیبی    ۱۸
۲-۵-  روشهای حل مسائل بهینهسازی ترکیبی    ۲۰
۲-۵-۱-  روش های ابتکاری    ۲۱
۲-۵-۱-۱-  آزادسازی    ۲۱
۲-۵-۱-۲-  تجزیه    ۲۲
۲-۵-۱-۳-  تکرار    ۲۲
۲-۵-۱-۴-  روش تولید ستون    ۲۲
۲-۵-۱-۵-  جستجوی سازنده     ۲۳
۲-۵-۱-۶-  جستجوی بهبود یافته    ۲۳
۲-۵-۱-۷-  روش جستجوی همسایه     ۲۴
۲-۵-۲-  روش‌های فرا ابتکاری  برگرفته از طبیعت    ۲۵
۲-۶-  جمع بندی    ۲۶
مراجع    ۲۷

مراجع

فصل اول: الگوریتم های فرا ابتکاری

۱-۱-  مقدمه

در سالهای دهه ۱۹۵۰ برنامه نویسی کامپیوترهای اولیه توسط تغییر سیم ها و تنظیم هزاران کلید و سوییچ انجام می شد. بعد از آن افراد به دنبال ابزارهای سریع تر و راحت تری برای برنامه نویسی بودند. در اواخر دهه ۱۹۵۰ مفسرهای زبان های طبیعی و کامپایلرهای پا به عرصه ظهور گذاشتند. در این سال ها بود که زبان های برنامه نویسی به منظور استفاده در دنیای نرم افزارهای تجاری عرضه شدند. این امر باعث شد تا آشنایی با زبان های برنامه نویسی به صورت عام در بین متخصصان رواج پیدا کند. بعد از این رویداد مهم  اکثر دانشمندان در زمینه های مختلف علمی سعی کردند از زبان برنامه نویسی استفاده کنند. یکی از موارد استفاده از زبان های برنامه نویسی، علم ریاضی و انجام محاسبات ریاضی بود. زمان حل بسیار کمتر این روش نسبت به حل دستی باعث شد تا سرعت استفاده از برنامه نویسی در شاخه های مختلف ریاضی  یه شدت رشد کند. در دهه ۱۹۷۰ برای اولین بار دانشمندان برای حل مسائل بهینه سازی ترکیبیاتی از الگوریتم های فرا ابتکاری استفاده کردند. آن ها برای پیاده سازی الگوریتم ها از زبان برنامه نویسی استفاده کردند. نتیجه این کار بدست آمدن جواب های مناسب در زمان مناسب برای مسائل بهینه سازی ترکیبیاتی با اندازه بزرگ بود. تا آن زمان برای این گونه مسائل به دلیل زمان حل بسیار زیاد جواب مناسبی یافت نشده بود.

۲-۱-  مرور ادبیات الگوریتم های فرا ابتکاری

در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند[۱] ایده استفاده از الگوریتم ژنتیک [۲]را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. الگوریتم ژنتیک نوع خاصی از الگوریتم های تکاملی است که از تکنیک های زیست‌شناسی فراگشتی مانند وراثت و جهش استفاده می‌کند. در واقع الگوریتم های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می کنند. الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. مختصراً گفته می‌شود که الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. در طبیعت، فرایند تکامل هنگامی ایجاد می‌شود که چهار شرط زیر برقرار باشد:

الف) یک موجود توانایی تکثیر داشته باشد (قابلیت تولید مثل).

ب) جمعیتی از این موجودات قابل تکثیر وجود داشته باشد.

پ) چنین وضعیتی دارای تنوع باشد.

ت) این موجودات به وسیله قابلیت‌هایی در زندگی از هم جدا شوند.

در طبیعت، گونه‌های متفاوتی از یک موجود وجود دارند که این تفاوت‌ها در کروموزوم‌های این موجودات ظاهر می‌شود و باعث تنوع در ساختار و رفتار این موجودات می‌شود.

این تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثیر می‌گذارد. موجوداتی که قابلیت‌ها و توانایی بیشتری برای انجام فعالیت‌ها در محیط دارند (موجودات متکامل‌تر)، دارای نرخ زاد و ولد بالاتری خواهند بود و طبعاً موجوداتی که سازگاری کمتری با محیط دارند، از نرخ زاد و ولد پایین‌تری برخوردار خواهند بود. بعد از چند دوره زمانی و گذشت چند نسل، جمعیت تمایل دارد که موجوداتی را بیشتر در خود داشته باشد که کروموزوم‌هایشان با محیط اطراف سازگاری بیشتری دارد. در طی زمان، ساختار افراد جامعه به علت انتخاب طبیعی تغییر می‌کند و این نشانه تکامل جمعیت است [۱,۲,۳] .

الگوریتم آنیلینگ شبیه‌سازی[۳] شده  توسط متروپولیس[۴] و همکاران در سال ۱۹۵۳ پیشنهاد شده و جهت بهینه‌سازی در سال ۱۹۸۳ مورد بازبینی قرار گرفته است. این روش در مسائل تاکسی تلفنی کاربرد دارد.

الگوریتم آنیلینگ شبیه‌سازی شده در شکل عمومی، بر اساس شباهت میان سرد شدن جامدات مذاب و حل مسائل بهینه‌سازی ترکیبی به وجود آمده است. در فیزیک مواد فشرده، گرم و سرد کردن فرایندی است فیزیکی که طی آن یک ماده جامد در ظرفی حرارت داده می‌شود تا مایع شود؛ سپس حرارت آن بتدریج کاهش می‌یابد. بدین ترتیب تمام ذرات فرصت می‌یابند تا خود را در پایین‌ترین سطح انرژی منظم کنند. چنین وضعی در شرایطی ایجاد می‌شود که گرمادهی کافی بوده و سرد کردن نیز به آهستگی صورت گیرد. جواب حاصل از الگوریتم گرم و سرد کردن شبیه‌سازی شده، به جواب اولیه وابسته نیست و می‌توان توسط آن جوابی نزدیک به جواب بهینه به دست آورد. حد بالایی زمان اجرای الگوریتم نیز قابل تعیین است. بنابراین الگوریتم گرم و سرد کردن شبیه‌سازی شده، الگوریتمی است تکراری که اشکالات روش‌های عمومی مبتنی بر تکرار را ندارد.

در روش آنیلینگ شبیه‌سازی شده، به صورت پی در پی از جواب جاری به یکی از همسایه‌های آن انتقال صورت می‌گیرد. این سازوکار توسط زنجیره مارکوف به صورت ریاضی قابل توصیف است. در این روش، یک مجموعه آزمون انجام می‌گیرد؛ این آزمون‌ها به نحوی است که نتیجه هر یک به نتیجه آزمون قبل وابسته است. در روش آنیلینگ شبیه‌سازی شده، منظور از یک آزمون، انتقال به نقطه جدید است و روشن است که نتیجه انتقال به نقطه جدید تنها وابسته به مشخصات جواب جاری است.

روش جستجوی همسایه و روش آنیلینگ شبیه‌سازی شده، هر دو روش‌های تکراری هستند. در الگوریتم آنیلینگ شبیه‌سازی شده، هر بار که شاخص کنترل‌کننده به مقدار نهایی خود می‌رسد، در حقیقت یک عملیات تکراری انجام شده است. در الگوریتم جستجوی همسایه، هنگامی که تعداد تکرارها به سمت بی‌نهایت میل می‌کند، روش به جواب بهینه نزدیک می‌شود. اما عملکرد الگوریتم آنیلینگ شبیه‌سازی شده سریع‌تر است [۴] .

دیکاستر[۵]و و تیمیس[۶]، اولین الگوریتم های ایمنی مصنوعی [۷]را در سال ۱۹۸۶ طراحی کردند. به طور کلی، سیستم‌های ایمنی مصنوعی جزء الگوریتم های الهام گرفته شده از بیولوژی هستند. این نوع الگوریتم‌ها، الگوریتم هایی کامپیوتری هستند که اصول و ویژگی‌های آنها نتیجه بررسی در خواص وفقی و مقاومت نمونه‌ها بیولوژیکی است. سیستم ایمنی مصنوعی نوعی الگو برای یادگیری ماشین است. یادگیری ماشین، توانایی کامپیوتر برای انجام یک کار با یادگیری داده‌ها یا از روی تجربه است. سیستم ایمنی مصنوعی توسط کاسترو به این صورت تعریف شده است:

سیستم های وفقی که با الهام از ایمونولوژی نظری و توابع، اصول و مدل های ایمنی سیستم بدن انسان مشاهده شده به وجود آمده‌اند و برای حل مسائل مورد استفاده قرار می‌گیرند [۵] .

الگوریتم جستجوی ممنوعه[۸] برای اولین بار در سال ۱۹۸۶ توسط گلووِر[۹] معرفی شد. روش جستجوی ممنوع همانند روش آنیلینگ شبیه‌سازی شده بر اساس جستجوی همسایه بنا شده است. در این روش عملکرد حافظه انسان شبیه‌سازی شده است. حافظه انسان با به کارگیری ساختمانی مؤثر و در عین حال ساده از اطلاعات، آنچه را در قبل رؤیت شده، ذخیره می‌کند. این مرکز همچنین فهرستی از حرکات منع شده را تنظیم می‌کند و این فهرست همواره بر اساس آخرین جستجوها منظم می‌شود. این روش از انجام هر گونه عملیات مجدد و تکراری جلوگیری می‌کند.

شکل نوین جستجوی ممنوع توسط گلوور مطرح شده است. روش جستجوی مبتنی بر منع، با ایجاد تغییری کوچک در روش جستجوی همسایه به وجود می‌آید. هدف این روش آن است که بخش‌هایی از مجموعه جواب که پیش از این بررسی نشده است، مد نظر قرار گیرد. بدین منظور حرکت به جواب‌هایی که اخیراً جستجو شده، ممنوع خواهد بود.

ساختار کلی روش جستجوی ممنوع بدین صورت است که ابتدا یک جواب اولیه امکان‌پذیر انتخاب می‌شود؛ سپس برای جواب مربوط، بر اساس یک معیار خاص مجموعه‌ای از جواب‌های همسایه امکان‌پذیر در نظر گرفته می‌شود.

در گام بعد، پس از ارزیابی جواب‌های همسایه تعیین شده، بهترین آنها انتخاب می‌شود و جابه‌جایی از جواب جاری به جواب همسایه انتخابی صورت می‌گیرد. این فرایند به همین ترتیب تکرار می‌شود تا زمانی که شرط خاتمه تحقق یابد.

در روش جستجوی ممنوع، فهرستی وجود دارد که جابه‌جایی‌های منع شده را نگهداری می‌کند و به فهرست تابو معروف است و کاربرد اصلی آن، پرهیز از همگرا شدن به جواب‌های بهینه محلی است. به عبارت دیگر، به کمک فهرست تابو جابه‌جایی به جواب‌هایی که اخیراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هایی از مجموعه جواب که پیش از این مورد بررسی قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جایی از جواب جاری به جواب همسایه امکان‌پذیر زمانی انجام می‌شود که در فهرست تابو قرار نداشته باشد. در غیر این صورت، جواب همسایه دیگری که در ارزیابی جواب‌های همسایه در رده بعدی قرار گرفته است، انتخاب شده و جابه‌جایی به آن صورت می‌گیرد.

در روش جستجوی ممنوع بعد از هر جابه‌جایی، فهرست تابو بهنگام می‌شود، به نحوی که جابه‌جایی جدید به آن فهرست اضافه شده و جابه‌جایی که تا n  تکرار مشخص در فهرست بوده است، از آن حذف می‌شود. نحوه انتخاب می‌تواند با توجه به شرایط و نوع مسأله متفاوت باشد    .[۶]

الگوریتم بهینه‌سازی کلونی مورچه‌ها[۱۰] در سال ۱۹۹۱ توسط دوریگو[۱۱] و همکاران پیشنهاد شده است که در حل مسأله فروشنده دوره‌گرد و مسائل تخصیص چندوجهی کاربرد دارد. الگوریتم بهینه ‌سازی کلونی مورچه‌ها از عامل‌های ساده‌ای که مورچه نامیده می‌شوند، استفاده می‌کند تا به صورت تکراری جواب‌هایی تولید کند. مورچه‌ها می توانند کوتاه‌ترین مسیر از یک منبع غذایی به لانه را با بهره‌گیری از اطلاعات فرمونی پیدا کنند. مورچه‌ها در هنگام راه رفتن، روی زمین فرمون می‌ریزند و با بو کشیدن فرمون ریخته شده بر روی زمین راه را دنبال می‌کنند؛ چنانچه در طی مسیر به سوی لانه به یک دوراهی برسند، از آن جایی که هیچ اطلاعی درباره راه بهتر ندارند، راه را به تصادف برمی‌گزینند. انتظار می‌رود به طور متوسط نیمی از مورچه‌ها مسیر اول و نیمی دیگر مسیر دوم را انتخاب کنند.

فرض می‌شود که تمام مورچه‌ها با سرعت یکسان مسیر را طی کنند. از آنجا که یک مسیر کوتاه‌تر از مسیر دیگر است، مورچه‌های بیشتری از آن می‌گذرند و فرمون بیشتری بر روی آن انباشته می‌شود. بعد از مدت کوتاهی مقدار فرمون روی دو مسیر به اندازه‌ای می رسد که روی تصمیم مورچه‌های جدید برای انتخاب مسیر بهتر تأثیر می‌گذارد. از این به بعد، مورچه‌های جدید با احتمال بیشتری ترجیح می‌دهند از مسیر کوتاه‌تر استفاده کنند، زیرا در نقطه تصمیم‌گیری مقدار فرمون بیشتری در مسیر کوتاه‌تر مشاهده می‌کنند. بعد از مدت کوتاهی تمام مورچه‌ها این مسیر را انتخاب خواهند کرد   .[۷]

[۱] John Holland

[۲] Genetic Algorithm

[۳] Simulated Annealing

[۴] Metropolis

[۵] Castro

[۶] Timmis

[۷] Artificial Immune

[۸] Tabu search

[۹] Glover

[۱۰] Ant Colony Optimization

[۱۱] Dorigo

تمامی فایل های پیشینه تحقیق و پرسشنامه و مقالات مربوطه به صورت فایل دنلودی می باشند و شما به محض پرداخت آنلاین مبلغ همان لحظه قادر به دریافت فایل خواهید بود. این عملیات کاملاً خودکار بوده و توسط سیستم انجام می پذیرد. جهت پرداخت مبلغ شما به درگاه پرداخت یکی از بانک ها منتقل خواهید شد، برای پرداخت آنلاین از درگاه بانک این بانک ها، حتماً نیاز نیست که شما شماره کارت همان بانک را داشته باشید و بلکه شما میتوانید از طریق همه کارت های عضو شبکه بانکی، مبلغ  را پرداخت نمایید.