این پایان نامه بصورت جامع و کامل به تشریح مفهوم بهینه سازی و بکارگیری آن در الگوریتمهای جستجو در قالب 3 فصل می پردازد
دانلود پایان نامه مهندسی نرم افزار
تشریح مفهوم بهینه سازی و بکارگیری آن در الگوریتمهای جستجو
*آپدیت:ضمیمه کردن مقاله ترجمه شده با عنوان Metaheuristics in Combinatorial Optimization در قالب 42 صفحه بصورت رایگان:)
قابل توجه مشتریان عزیز:هم فایل انگلیسی و هم فارسی ضمیمه شده است.
چکیده
بهینهسازی یک فعالیت مهم و تعیینکننده در طراحی ساختاری است. طراحان زمانی قادر خواهند بود طرحهای بهتری تولید کنند که بتوانند با روشهای بهینهسازی در صرف زمان و هزینه طراحی صرفهجویی نمایند. بسیاری از مسائل بهینهسازی در مهندسی، طبیعتاً پیچیدهتر و مشکلتر از آن هستند که با روشهای مرسوم بهینهسازی نظیر روش برنامهریزی ریاضی و نظایر آن قابل حل باشند.
بهینهسازی ترکیبی (Combinational Optimization)، جستجو برای یافتن نقطه بهینه توابع با متغیرهای گسسته (Discrete Variables) میباشد. امروزه بسیاری از مسائل بهینهسازی ترکیبی که اغلب از جمله مسائل با درجه غیر چندجملهای (NP-Hard) هستند، به صورت تقریبی با کامپیوترهای موجود قابل حل میباشند. از جمله راهحلهای موجود در برخورد با این گونه مسائل، استفاده از الگوریتمهای تقریبی یا ابتکاری است. این الگوریتمها تضمینی نمیدهند که جواب به دست آمده بهینه باشد و تنها با صرف زمان بسیار میتوان جواب نسبتاً دقیقی به دست آورد و در حقیقت بسته به زمان صرف شده، دقت جواب تغییر میکند.
کلمات کلیدی:
بهینه سازی
الگوریتمهای جستجو
سیستم های نرم افزاری
مقدمه
هدف از بهینهسازی یافتن بهترین جواب قابل قبول، با توجه به محدودیتها و نیازهای مسأله است. برای یک مسأله، ممکن است جوابهای مختلفی موجود باشد که برای مقایسه آنها و انتخاب جواب بهینه، تابعی به نام تابع هدف تعریف میشود. انتخاب این تابع به طبیعت مسأله وابسته است. به عنوان مثال، زمان سفر یا هزینه از جمله اهداف رایج بهینهسازی شبکههای حمل و نقل میباشد. به هر حال، انتخاب تابع هدف مناسب یکی از مهمترین گامهای بهینهسازی است.
در این گزارش ابتدا به بررسی تعاریف مختلف بهینه سازی پرداخته و سپس تعریف مورد قبول که پایه بخشهای بعدی قرار میگیرد انتخاب می شود. سپس به معرفی تکنیک های مورد استفاده در سیستم های نرم افزاری پرداخته و تمرکز مطالب بر روی تکنیک جستجو قرار می گیرد. یکی از (و قطعاُ مهمترین) مفاهیم مطرح در تحقیق عملیات مفهوم بهینه سازی است. بهینه سازی را میتوان تخصیص منابع به مصارف به بهترین شکل ممکن تعریف کرد. نکته اساسی در این تعریف رسیدن به بهترین تخصیص ممکن است، بطوریکه تخصیصی بهتر از آن وجود نداشته باشد. استفاده از روشهای اولیه بهینه سازی شامل برنامه ریزی خطی ، برنامه ریزی عدد صحیح ، برنامه ریزی پویا ، و برنامه ریزی غیر خطی با مشکلاتی همراه بود و مهمترین این مشکلات وقت¬گیر بودن حل مسائل بزرگ با آنها بود.
به گونه ای که حتی با تکنولوژیهای محاسباتی پیشرفته امروزی حل یک مساله با ابعاد وسیع با تکنیکهای ذکر شده به چندین سال زمان نیاز دارد. بروز این مشکل به توهماتی که در ابتدای شکل گیری دانش تحقیق در عملیات، مبنی بر حل بهینه تمام مسائل دنیا با استفاده از این دانش، ایجاد شده بود پایان داد. بروز این مشکل، همچنین، سبب شد محققان مجبور به تعدیل انتظارات خود از این دانش جدید در یافتن بهترین جواب ممکن شوند و به جوابهایی به اندازه کافی خوب، که حتی درمورد مسائل با ابعاد بزرگ نیز در مدت زمان منطقی میتوان به آنها رسید، اکتفا کنند.
فهرست مطالب
فصل اول:بهینه سازی و انواع آن
چکیده
. مقدمه
هدف
بررسی روشهای جستجو و بهینهسازی
شکل ـ : طبقه بندی انواع روشهای بهینه سازی
روشهای شمارشی
روشهای محاسباتی (جستجوی ریاضی یا Based Method Calculus)
مسائل بهینه سازی ترکیبی (Optimization Problems Combinational)
روش حل مسائل بهینهسازی ترکیبی
آزادسازی
تجزیه
تکرار
روش تولید ستون (Column Generation)
جستجوی سازنده (Constructive Search)
جستجوی بهبود یافته (Improving Search)
روش جستجوی همسایه ( NS= Neighbourhood Search)
روشهای فرا ابتکاری (Metaheuristic) برگرفته از طبیعت
معرفی
مسأله فروشنده دوره گرد (Travelling Salesman Problem = TSP)
انواع روشهای فرا ابتکاری برگرفته از طبیعت
الگوریتم ژنتیک
آنیلینگ شبیهسازی شده
شبکههای عصبی
جستجوی ممنوع
سیستم مورچه (Ant System)
فصل دوم: سیستم های نرم افزاری و بهینه سازی آنها
. انواع سیستم های نرم افزاری
. مقدمه
. انواع سیستم های نرم افزاری
. . سیستم تصمیم یار(DSS)
. . . ویژگیها و قابلیتهای DSS
. . . زیرسیستم های DSS
. . سیستم خبره
. . . ساختار سیستم های خبره
. بهینه سازی در سیستم های رابطه ای
. . مروری بر پردازش پرس و جو
. . بهینه سازی پرس و جو
فصل سوم: جستجو
. . روشهای جستجوی ساخت یافته
. . . جستجوی اول بهترین
. . . . کمینه کردن هزینه تخمینی برای رسیدن به یک هدف : جستجوی حریصانه
. . . . کمینه کردن هزینه کل مسیر: جستجوی A*
. . . جستجو با حافظه محدود
. . . . جستجوی A* عمقی تکراری (IDA*)
. . . . جستجوی A* ساده شده با محدودیت حافظه SMA*))
. . . الگوریتم های بهبود تکرار شونده
. . . الگوریتم ژنتیک
. . جستجوی توزیع شده (الگوریتمهای جستجو در عاملها)
. . . تعریف مساله ارضای محدودیت (CSP)
. . . الگوریتم تصفیه
. . . الگوریتم سازگاری برمبنای فرااستدلال
. . . عقبگرد آسنکرون
. . . جستجوی الزام ضعیف آسنکرون
. . مساله یافتن مسیر
. . . تعریف مساله یافتن مسیر
. . . برنامه نویسی پویای آسنکرون
. . . A* بی درنگ یادگیر(LRTA*)
. . . A* بی درنگ(RTA*)
. . . جستجوی هدف متحرک(MTS)
. . . جستجوی دوطرفه بی درنگ(RTBS)
. . . جستجوی چندعامله بی درنگ
. . بازیهای دو نفره
. . . فرموله کردن بازیهای دو نفره
. . . رویه Minimax
. . . هرس βα
. فرااکتشافات در بهینه سازی ترکیبی
. . تعاریف اولیه
. . طبقه بندی فرااکتشافات
. . روشهای خط سیر
. . . جستجوی محلی پایه
. . . آنیلینگ شبیه سازی شده
. . . جستجوی ممنوع
. . . روشهای جستجوی محلی کاوشگرانه
. . . . GRASP
. . . . جستجوی همسایگی متغیر
. . . . جستجوی محلی هدایت شده
. . . . جستجوی محلی تکراری
. . روشهای مبنی بر جمعیت
. . . محاسبه تکاملی
. . . . جستجوی پخشی و اتصال مجدد مسیر
. . . . الگوریتم های تقریب توزیع
. . . بهینه سازی گروه مورچه ها(ACO)
. . دیدگاه متمرکزسازی و متنوع سازی
. . . متمرکزسازی و متنوع سازی
. . . کنترل استراتژیک متمرکزسازی و متنوع سازی
. . . ترکیب فرااکتشافات
. خلاصه و نتیجه گیری
. مراجع