نوع فایل: word
قابل ویرایش 78 صفحه
مقدمه:
در بسیاری از مقالات مسائلی به چشم می خورند که جزو مسائلNP-Hard یا NP-Complete عنوان شده اند. مسائلی همچون: مسئله فروشنده دوره گرد - مسئله N وزیر- مسئله کوله پشتی - مسئله سیکل هامیلتونی - مسئله ضایعات برش دوبعدی و مسئله رنگ آمیزی گراف از این جمله اند. خصوصیت مشترک این مسائل آن است که الگوریتم شناخته شده ای با مرتبه زمانی چند جمله ای برای حل آنها هنوز پیدا نشده است. زمان اجرای الگوریتم های با مرتبه زمانی غیر چند جمله ای به سرعت و حتی با افزایش کم اندازه مسئله زیاد می شود و این یعنی سریعترین کامپیوترهای ترتیبی هر زمان فقط قادر به حل مسائلی کوچک از این رده خواهند بود. هدف این نوشتار آشنایی با مفاهیم NP-Hard و NP-Complete می باشد.
فهرست مطالب:
فصل اول: آشنایی با مسائل NP-Hard, NP-Complete
1- مقدمه
2- الگوریتمهای غیر قطعی
3- آشنایی با مسائلNP
4- مسائل NP-Complete
فصل دوم : مفهوم پردازش تکاملی( ( Evolution computing
1- جایگاهEC(مفهوم اصلی پردازش تکاملی و جایگاه آن در طبیعت)
2- تاریخچه مختصر
3- الهام از بیولوژی
- 1 - تئوری تکامل داروین (به صورت ساده)
- 2- ژنتیک (به صورت ساده)
4- انگیزه برای مطالعه EC
فصل سوم: الگوریتمهای تکاملی( Evolution ALGORITM )
1-شمای کلی یک الگوریتم تکاملی
2-مولفه های اصلی الگوریتم تکاملی
-نحوه بازنمایی ( تعریف جمعیت اولیه )
-تابع برازندگی ( تابع ارزیابی )
-جمعیت
-مکانیزم انتخاب والد
-عملگرهای ژنتیکی (برش و جهش )
-مکانیزم انتخاب بازمانده
-شرایط توقف
3- انواع مختلف الگوریتمهای تکاملی( GA – EP – GP – ES)
4-الگوریتمهای ژنتیک
مقدمه ای بر ژنتیک
راحل الگوریتمهای ژنتیک
را از الگوریتم ژنتیک استفاده می کنیم ؟
عریف
ازنمایی
ملگر برش ( Crossover ) تک نقطه ای
ملگر جهش (Mutation)
لگر انتخاب SGA
روشهای بازنمایی – رشته های باینری (کدگری)
- بازنمایی اعداد صحیح
- بازنمایی جایگشتی
ملگرهای جهش برای بازنمایی جایگشتی
هش درجی
هش تعویضی
هش وارونه سازی
جهش Scramble
عملگرهای crossover برای بازنمایی جایگشتی
Order 1 crossover
PM x crossover
Cycle crossover
Edge crossover
عملگرهای crossover برای بازنمایی باینری
Crossover تک نقطه ای
N-Point Crossover
Uniform Crossover
انواع روشهای انتخاب برای الگوریتم های ژنتیک
Roulette Wheel Selection -1
Rank Selection-2
State Selection -3
Tournament Selection-4
فصل چهارم: طراحی الگوریتمهای ژنتیک برای مسائل کوله پشتی و nوزیر
1- مسئله n وزیر
نحوه بازنمایی
عملگرهای ژنتیکی (جهش – برش)
عملگرهای انتخاب ( انتخاب والد – انتخاب بازمانده)
ایجاد جمعیت اولیه و شرایط توقف
تابع برازندگی
2-آشنایی با مسائل کوله پشتی و حل آن با استفاده از لگوریتمهای ژنتیک
نحوه بازنمایی
عملگرهای ژنتیکی (جهش – برش)
عملگرهای انتخاب (انتخاب والد – انتخاب بازمانده)
ایجاد جمعیت اولیه و شرایط توقف
تابع برازندگی
فصل پنجم: کد های مربوط به پیاده سازی الگوریتم Nوزیر با الگوریتم های ژنتیک ..52
کد های مربوط به پیاده سازی الگوریتم Nوزیر با دلفی
کد های مربوط به پیاده سازی الگوریتم Nوزیر با C++z
منابع و مراجع
فصل اول: آشنایی با مسائل NP-Hard, NP-Complete
1- مقدمه
2- الگوریتمهای غیر قطعی
3- آشنایی با مسائلNP
4- مسائل NP-Complete
منابع و مأخذ:
- طراحی الگوریتم . جعفرنژاد قمی.فصل مربوط به مسائل NP_HARD
2-I.RECHENBERG.EVOLUTIONSTRATEGIE:OPTIMIERUNG TECHNISHER SYSTEM NATCH PRINZIPIEN DES BIOLOGISCHEN EVOLUTION.
3-H._P.SCHWEFEL.EVOLUTION AND OPTIMNM SEEKING.WILEY,NEW YOURK.1995
4-L.J.FOGEL, A.J.OWENS,M.J.WALSH.ARTIFICIAL INTELLIGENCE THROUGH A IMULATION OF EVOLUTION.
5-.T.E.DAVIS,J.C.PRINCIPE.A MARKOV CHAIN FRAMEWORK FOR THE SIMPLE GENETIC ALGORITM.EVOLUTIONARY COMPUTATION
6-J.H.HOLLAND.ADAPTION IN NATURAL AND ARTIFICIAL SYSTEMS.MIT PRESS,CAMBRIDGE,MA,1992.
7-W.BANZHAF,P.NORDIN,R.E.KELLER,F.D.FRANCONE.GENETIC PROGRAMMING:AN INTRODUCTION.MORGAN KAUFMANN,SAN FRANCISCO,1998.
8- J.H.HOLLAND. ADAPTION IN :ROSEN,SNELL,EDS.,PROGRESS IN THEORETICAL BIOLOGY:4.PLENUM,1976
9-T.BACK,D.B.FOGEL,Z.MICHALEWICZ,EDSEVOLUTIONARY COMPUTATIO 1:BASIC ALGORITHMS AND OPERATORS.INSTITUTE OF PHYSICS PUBULISHING,BRISTOL,2000.
10-Z.MICHALEWICZ.GENETIC ALGORITM+DATA STRUCTURES=EVOLUTIONPROGRAMS.SPRINGER,BERLIN,HEIDELBERG,NEW YORK,3RD EDN.,1996
11-A.E.EIBEN,Z.MICHALEWICZ,EDS.EVOLUTIONARY COMPUTATION.IOS PRESS,1998
12-C.DARWIN.THE ORIGIN OF SPECIES.JOHN MURRAY,1859
13- A.E.EIBEN,E.H.L.Aarts,K.M.VAN HEE. GLOBAL CONVERGENCE OF GENETIC ALGORITM :A MARKOV CHAIN ANALYSIS .
14- A.E.EIBEN.MULTIPARENT RECOMBINATION .
15-2000 CONGRESS ON EVOLUTIONARY COMPUTATION (CEC'2000).IEEE PRESS,PISCATAWAY,NJ,1999
16--J.H.HOLLAND.ADAPTION IN NATURAL AND ARTIFICIAL SYSTEMS.MIT PRESS,CAMBRIDGE,MA,1992.
17-L.DAVIS,ED.HANDBOOK OF GENETIC ALGORITMS.VAN NOSTRAND REINHOLD,1991
18-I.M.OLIVER,D.J.SMITH,J.HOLLAND.A STUDY OF PERMUTATION CROSSOVER OPERATORS ON THE TRAVELLING SALESMAN PROBLEM.
19-D.WHITLEY.PERMUTATIONS
20-G.SYSWERDA.SCHEDULE OPTIMISATION USING GENETIC ALGORITHMS
پروژه الگوریتم های ژنتیک و حل مسائل((NP_HARD)). doc