بررسی حل مسائل مختلف مسیر یابی با استفاده از الگوریتم ژنتیک
چکیده:
یکی از انواع مسائل مطرح شده در ارتباط با جستجو در میان همسایگی‌های نزدیک، مسیریابی بهینه در میان نقاط مکانی با ترتیب مشخص یا همان (OSR) Optical Sequenced Route است. درخواست برای یافتن مسیر بهینه با توالی نقاط مشخص (OSR) در واقع جستجو برای یافتن مسیری است که دارای کمترین طول بوده و از یک مبدأ مکانی معلوم آغاز شده و از نقاط مکانی مشخصی با ترتیب خاص بسته به نوع مکان‌ها عبور کرده باشد. ترتیب این نقاط مکانی با توجه به مشخصه‌های از پیش تعیین شده مسأله بوده و قابل تغییر نمی‌باشد. مسأله OSR قابل تبدیل به مسأله یافتن کوتاه‌ترین مسیر در یک گراف مسطح بزرگ است. یافتن کوتاه‌ترین مسیر از طریق الگوریتم‌های کلاسیک مانند Dijkstra برای بسیاری از مسائل موجود در دنیای واقعی عملی نیست. مسیریابی OSR در مقاله مطرح گردیده و دو روش در فضای برداری و متریک برای آن پیشنهاد شده است. در این مقاله پیاده‌سازی این مسیریابی توسط الگوریتم ژنتیک انجام شده است.
فهرست مطالب:
چکیده
فصل اول
1-1مقدمه
تاریخچه
2-1 انتخاب طبیعی
3-1 کد کردن
4-1 شما
5-1 ایجاد جمعیت اولیه
6-1 عملگرهای برشی
7-1 عملگرهای جهشی
8-1 خلاصه ویژگی‌ها
9-1 مکانیزمهای انتخاب
انتخاب قطع سر
10-1 انتخاب قطعی بریندل
11-1 انتخاب نخبه‌گرا
12-1 انتخاب جایگزینی نسلی اصلاح شده
13-1 انتخاب مسابقه
14-1 انتخاب مسابقه تصادفی
15-1 مکانیزمهای برش
16-1 یک نقطه برش
17-1 دو نقطه برش
18-1 بخش-نگاشته
19-1 ترتیب
20-1 برش یکنواخت
21-1 چرخه
22-1 محدب
23-1 مکانیزمهای جهش
24-1 استراتژی برخورد با محدودیت‌ها
25-1 استراتژی اصلاح عملگرهای ژنتیک
26-1 استراتژی ردی
27-1 استراتژی اصلاحی
28-1 استراتژی جریمه‌ای
29-1 کدکردن
1-29-1کدینگ جایگشتی
2-29-1 کدگذاری مقدار
3-29-1 کدینگ درخت
4-29-1 آرایه
5-29-1 لیست
6-29-1 درخت
فصل دوم
1-2 مقدمه
2-2 اصول عملکرد
1-2-2 الگوریتم های LS
2-2-2 الگوریتم های Dijkstra
3-2-2 الگوریتم های DV
مسیر یابی سلسله یابی
فصل سوم
کد سورس
1-3 مقدمه
فصل چهارم
نتیجه گیری
پیوستها
منابع و مآخذ
تعداد مشاهده: 1893 مشاهده
فرمت فایل دانلودی:.docx
فرمت فایل اصلی: docx
تعداد صفحات: 67
حجم فایل:1,873 کیلوبایت
-
راهنمای استفاده:
مناسب جهت استفاده دانشجویان رشته کامپیوتر و فناوری اطلاعات
-
محتوای فایل دانلودی:
در قالب فایل word قابل ویرایش
پروژه الگوریتم ژنتیک (GA)
چکیده:
الگوریتم ژنتیک (Genetic Algorithm- GA) تکنیک جستجویی در علم رایانه برای یافتن راه حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند.
در واقع الگوریتم های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای تصادف هستند. مختصراً گفته می‌شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسأله‌ای که باید حل شود ورودی است و راه‌حل‌ها طبق یک الگو کد گذاری می‌شوند که تابع fitness نام دارد هر راه حل کاندید را ارزیابی می‌کند که اکثر آنها به صورت تصادفی انتخاب می‌شوند. کلاً این الگوریتم‌ها از بخش های تابع برازش، نمایش، انتخاب، تغییر تشکیل می شوند.
فهرست مطالب:
چکیده
فصل اول
1-1- مقدمه
1-2- به دنبال تکامل
1-3- ایدۀ اصلی استفاده از الگوریتم ژنتیک
1-4- درباره علم ژنتیک
1-5- تاریخچۀ علم ژنتیک
1-6- تکامل طبیعی (قانون انتخاب طبیعی داروین)
1-7- رابطه تکامل طبیعی با روشهای هوش مصنوعی
1-8- الگوریتم
1-8-1- الگوریتم‌های جستجوی ناآگاهانه
1-8-1-الف- جستجوی لیست
1-8-1-ب- جستجوی درختی
1-8-1-پ- جستجوی گراف
1-8-2- الگوریتم‌های جستجوی آگاهانه
1-8-2-الف- جستجوی خصمانه
1-9- مسائل NP-Hard
1-10- هیوریستیک
1-10-1- انواع الگوریتم‌های هیوریستیک
فصل دوم
2-1- مقدمه
2-2- الگوریتم ژنتیک
2-3- مکانیزم الگوریتم ژنتیک
2-4- عملگرهای الگوریتم ژنتیک
2-4-1- کدگذاری
2-4-2- ارزیابی
2-4-3- ترکیب
2-4-4- جهش
2-4-5- رمزگشایی
2-5- چارت الگوریتم به همراه شبه کد آن
2-5-1- شبه کد و توضیح آن
2-5-2- چارت الگوریتم ژنتیک
2-6- تابع هدف
2-7- روشهای کد کردن
2-7-1- کدینگ باینری
2-7-2- کدینگ جایگشتی
2-7-3- کد گذاری مقدار
2-7-4- کدینگ درخت
2-8- نمایش رشته‌ها
2-9- انواع روشهای تشکیل رشته
2-10- باز گرداندن رشته‌ها به مجموعه متغیرها
2-10-1- تعداد بیت‌های متناظر با هر متغیر
2-11- جمعیت
2-11-1- ایجادجمعیت اولیه
2-11-2- اندازه جمعیت
2-12- محاسبه برازندگی (تابع ارزش)
2-13- انواع روشهای انتخاب
2-13-1- انتخاب چرخ رولت
2-13-2- انتخاب حالت پایدار
2-13-3- انتخاب نخبه گرایی
2-13-4- انتخاب رقابتی
2-13-5- انتخاب قطع سر
2-13-6- انتخاب قطعی بریندل
2-13-7- انتخاب جایگزینی نسلی اصلاح شده
2-13-8- انتخاب مسابقه
2-13-9- انتخاب مسابقه تصادفی
2-14- انواع روشهای ترکیب
2-14-1- جابه‌جایی دودوئی
2-14-2- جابه‌جایی حقیقی
2-14-3- ترکیب تک‌نقطه‌ای
2-14-4- ترکیب دو نقطه‌ای
2-14-5- ترکیب n نقطه‌ای
2-14-6- ترکیب یکنواخت
2-14-7- ترکیب حسابی
2-14-8- ترتیب
2-14-9- چرخه
2-14-10- محدّب
2-14-11- بخش_نگاشته
2-15- احتمال ترکیب
2-16- تحلیل مکانیزم جابجایی
2-17- جهش
2-17-1- جهش باینری
2-17-2- جهش حقیقی
2-17-3- وارونه سازی بیت
2-17-4- تغییر ترتیب قرارگیری
2-17-5- وارون سازی
2-17-6- تغییر مقدار
2-18- محک اختتام اجرای الگوریتم ژنتیک
2-19- انواع الگوریتم‌های ژنتیکی
2-19-1- الگوریتم ژنتیکی سری
2-19-2- الگوریتم ژنتیکی موازی
2-20- مقایسه الگوریتم ژنتیک با سیستم‌های طبیعی
2-21- نقاط قوّت الگوریتم‌های ژنتیک
2-22- محدودیت‌های GA ها
2-23- استراتژی برخورد با محدودیت‌ها
2-23-1- استراتژی اصلاح عملگرهای ژنتیک
2-23-2- استراتژی رَدّی
2-23-3- استراتژی اصلاحی
2-23-4- استراتژی جریمه‌ای
2-24- بهبود الگوریتم ژنتیک
2-25- چند نمونه از کاربردهای الگوریتم‌های ژنتیک
فصل سوم
3-1- مقدمه
3-2- حلّ معمای هشت وزیر
3-2-1- جمعیت آغازین
3-2-2- تابع برازندگی
3-2-3- آمیزش
3-2-4- جهش ژنتیکی
3-3- الگوریتم ژنتیک و حلّ مسألۀ فروشندۀ دوره‌گرد
3-3-1- حل مسأله TSP به وسیله الگوریتم ژنتیک
3-3-2- مقایسه روشهای مختلف الگوریتم و ژنتیک برای TSP
3-3-3- نتیجه گیری
3-4- حلّ مسأله معمای سودوکو
3-4-1- حل مسأله
3-4-2- تعیین کروموزم
3-4-3- ساختن جمعیت آغازین یا نسل اول
3-4-4- ساختن تابع از ارزش
3-4-5- ترکیب نمونه‌ها و ساختن جواب جدید
3-4-6- ارزشیابی مجموعه جواب
3-4-7- ساختن نسل بعد
3-5- مرتب سازی به کمک GA
3-5-1- صورت مسأله
3-5-2- جمعیت آغازین
3-5-3- تابع برازندگی
3-5-4- انتخاب
3-5-5- ترکیب
3-5-6- جهش
فهرست منابع و مراجع
پیوست
واژه‌نامه
تعداد مشاهده: 2372 مشاهده
فرمت فایل دانلودی:.docx
فرمت فایل اصلی: docx
تعداد صفحات: 153
حجم فایل:963 کیلوبایت
-
راهنمای استفاده:
الگوریتمی مناسب برای بهینه سازی کلیه توابع و اهداف، مناسب دانشجویان رشته کامپیوتر و فناوری اطلاعات
-
محتوای فایل دانلودی:
در قالب فایل word و قابل ویرایش