|
بررسی آلگوریتم ژنتیک در زبان برنامه نویسی C++
پایان نامه بررسی آلگوریتم ژنتیک در زبان برنامه نویسی C در 140 صفحه ورد قابل ویرایش
|
|
| دسته بندی | فنی و مهندسی |
| فرمت فایل | doc |
| حجم فایل | 249 کیلو بایت |
| تعداد صفحات فایل | 140 |
بررسی آلگوریتم ژنتیک در زبان برنامه نویسی C++
چکیده
علم ژنتیک، علمی است که به تازگی وارد علوم کامپیوتر شده و با استفاده از اجزا مورد نیاز ژنتیک و شبیه سازی آن در کامپیوتر، انسان را قادر می سازد تا بعضی از مسائل مختلف و پیچیده ای که در اوایل حل نشدنی بودند، را حل کند.
این مستند، یک کتابخانه از اشیا الگوریتم ژنتیک به زبان c++ می باشد. این کتابخانه شامل ابزاریست که برای بهبود هر برنامه ای به زبان c++ و هر خروجی و هر عملگر ژنتیکی، استفاده می شوند. در اینجا، با پیاده سازی الگوریتم ژنتیک، رابط برنامه نویسی آن و اشکالی برای راهنمایی، آشنا خواهید شد.
مقدمه
این مستند محتویات کتابخانه الگوریتم ژنتیک را رمز بندی می کند و بعضی از فلسفه های طراحی را که در پشت پیاده سازی هستند، نمایش می دهد. بعضی از مثال های کد منبع در آخر صفحه مشخص شده تا ساختار اصلی برنامه، توانایی های عملگرها، تطابق عملگرها با نیاز کاربر و مشتقاتی از کلاس های جدید مجموعه ژن را نمایش بدهند. وقتی که شما از یک کتابخانه استفاده می کنید به صورت ابتدایی با دو نوع کلاس کار می کنید الگوریتم مجموعه ژن و الگوریتم ژنتیک. هر نمونه ای از مجموعه ژن یک راه حل برای مسئله شما نشان می دهد. شی الگوریتم ژنتیک توضیح می دهد که چگونه سیر تکامل باید طی شود. الگوریتم ژنتیک از یک تابع عضو شی ای که توسط شما تعریف شده است استفاده می کند تا معین کند چگونه هر مجموعه ژن برای زنده ماندن مناسب است؟
الگوریتم ژنتیک از عملگر های مجموعه ژن ( که در داخل مجموعه هستند) و استراتژی های انتخاب/ جایگزینی ( که در داخل الگوریتم ساخته می شود ) برای تولید یک مجموعه ژن جدید مجزا ، استفاده می کند.
سه چیز برای حل مسئله با استفاده از الگوریتم ژنتیک وجود دارد :
1. تعریف خروجی های که نشان داده میشوند
2. تعریف عملگر های ژنتیکی
3. تعریف تابع عضو شی را
GALIB (کتابخانه الگوریتمهای ژنتیک ) به شما در دومورد اول به وسیله مهیا کردن مثال های زیاد وتکه برنامه هایی که شما می توانید ، خروجی ها و عملگر های خود را بسازید کمک می کند . در خیلی از موارد شما می توانید از ساختار خروجی ها و عملگر ها با کمی یا هیچ اصلاحی استفاده کنید . تابع عضو شی کاملا به شما مربوط می شود .
در صورتی که شما خروجی ها ، عملگرها و موارد شی را داشته باشید ، می توانید هر کدام از الگوریتم های ژنتیک را برای پیدا کردن راه حل بهتر و مناسبتر برای مسئله تان به کار بگیرید. موقعی که شما از الگوریتم ژنتیک برای حل یک مشکل بهینه استفاده می کنید، باید قادر باشید که یک راه حل برای مسئله در یک ساختمان داده ارائه بدهید . الگوریتم ژنتیک یک جمعیت از راه حل هایی که بر طبق نمونة ساختمان دادهایی که به وجود آورده اید، ایجاد می کند . بعد الگوریتم ژنتیک بر روی این جمعیت عمل می کند تا بهترین راه حل را ازآن استخراج کند.در GALIB کتابخانه الگوریتم ژنتیک به نمونة ساختمان داده GAGENOME گفته می شود (بعضی ها به آن کروموزوم نیز می گویند ). این کتابخانه شامل چهار نوع از این مجموعه هاست GALISTGENOME ( لیست پیوندی مجموعه ژن)GATREEGAGENOME (درخت مجموعه ژن) GAARRYGENOME( آرایه مجموعه ژن) GABINARYSTRINGGENOME(رشته دودویی مجموعه ژن). این کلاس ها از کروموزوم یا کلاس GAGENOME اصلی و یک کلاس ساختمان داده ای که بوسیله نامشان مشخص شده اند، مشتق شده اند.
برای مثال لیست پیوندی مجموعه ژن از کلاس GALIST و همچنین کلاس مجموعه ژن GAGENOME مشتق شده است. از ساختمان داد ه ای که با تعریفات مسئله شما همخوانی دارد، استفاده کنید. برای مثال ، اگر شما سعی می کنید که یک تابعی را بهینه سازی کنید که به پنج عدد حقیقی وابسته است ، پس به عنوان مجموعه ژن خود از یک آرایه یک بعدی با پنج عنصر اعشاری استفاده کنید.
الگوریتم های ژنتیک مختلف زیادی وجود دارند. GALIB (کتابخانه الگوریتم ژنتیک) شامل سه نوع اصلی می باشد:
1. حالت ساده
2. حالت ساکن یا ثابت یا یکنواخت
3. حالت افزایش
این الگوریتم ها در طریق های که مجموعه های جدید مجاز را ایجاد می کند ومجموعه های قدیمی را درزمان سیرتکامل جایگزین می کنند ، با یکدیگر تفاوت دارند.
GALIB دو مکانیسم اولیه برای گسترش قابلیت های ساخت شی را مهیا می کند اول از همه (و مهمتر از همه از نظر برنامه نویسی C++ ) شما می توانید کلاس های خودتان را درست کنید و تابع های عضو جدیدی را تعریف کنید . اگر شما احتیاج دارید که فقط تنظیمات کمی را بر روی رفتار کلاس GALIB اعمال کنید ، در بیشتر موارد می توانید یک تابع تعریف کنید و به کلاس GALIB بگویید که از آن به عنوان پیش فرض استفاده کند .
الگوریتم های ژنتیک اگر به درستی پیاده سازی شوند، قابلیت هر دو مورد پویش( پیدا کردن وسیع)و کاوش (پیداکردن محلی )در فضای SEARCH را، دارند. نوع رفتار یا عملکردی را که شما می بینید، بستگی به این دارد که چگونه عملگرها کار می کنند و همچنین بستگی به شکل یا فرم فضای SEARCH شما دارد.
تابع score:
بااستفاده از تابع شی‌گرایی اختصاص داده شده به کروموزوم امتیاز شی‌گرایی کروموزوم را بر می‌گرداند. اگر هیچ تابعی شی‌ای اختصاص داده نشده و هیچ امتیازی قرار داده نشده، امتیاز صفر برگردانده می‌شود. اگر تابع امتیاز با یک ورودی فراخوانی شود، امتیاز شی‌ای کروموزوم همان مقدار ورودی خواهد شد. (این مورد برای توابع شی‌ای پایه بر جمعیت مفید است زیرا در‌آن شی جمعیت عمل تکامل را انجام میدهد)
تابع userdata :
هر کروموزوم شامل یک اشاره‌گر کلی به داده‌های مشخص شده برای کاربر می‌باشد. از این تابع عضو برای قرار دادن و دریافت این اشاره‌گر استفاده می‌شود. در نظر داشته باشید که کپی کردن یک کروموزوم باعث می‌شود که کروموزوم کپی شده به همان اشاره‌گر داده‌ای کاربر به عنوان اشاره‌گر اصلی مراجعه می‌کند و داده کاربر کپی نمی‌شود. در نتیجه تمام کروموزومها در جمعیت به همان داده کاربر اشاره می‌کنند.
تابع write :
محتویات کروموزوم رابه جریان مخصوص و معینی می‌فرستد.
GA1DArrayGenome<T>
آرایه یک بعدی کروموزوم یک آرایه از اشیاء‌جنسی کلی و دوباره قابل اندازه‌گیری می‌باشد. این آرایه متشکل از کلاس GAGenome و کلاس GAArray<> می‌باشد.
هر عنصر در این آرایه یک ژن است. ارزش ژنها توسط نوع کروموزوم تعیین می‌شود. برای مثال، یک آرایه از اعداد صحیح مقادیر صحیح را دارد در صورتیکه آرایه از اعشار مقادیر اعشاری را داراست.
سلسله مراتب کلاس
class GA1DArrayGenome<T> : public GAArray<T>, public GAGenome
سازنده ها
GA1DArrayGenome(unsigned int length, GAGenome::Evaluator objective = NULL, void * userData= NULL)
GA1DArrayGenome(const GA1DArrayGenome<T> &)
شاخص توابع عضو
const T & gene(unsigned int x=0) const
T & gene(unsigned int x=0)
T & gene(unsigned int x, const T& value) const
T & operator[](unsigned int x) const
T & operator[](unsigned int x)
int length() const
int length(int l)
int resize(int x)
int resizeBehaviour() const
int resizeBehaviour(unsigned int minx, unsigned int maxx)
void copy(const GA1DArrayGenome<T>& original, unsigned int dest, unsigned int src,
unsigned int length)
void swap(unsigned int x1, unsigned int x2)
توضیحات توابع عضو :
تابع copy :
بیت‌های مشخص شده را از کروموزوم طراحی شده کپی می‌کند.
تابع gene:
قرار دادن یا دریافت عنصری مشخص
تابع length:
قرار دادن یا گرفتن طول
تابع resize:
قرار دادن و طول.
تابع resizeBehavior :
قرار دادن یا گرفتن رفتار دوباره اندازه شده. مقدارmin , ،مینیمم طول اجازه داده شده و مقدار max ، ماکسیم طول اجازه داده شده را تعیین می‌کنند. اگر مقادیر max,min مساوی باشند،کروموزوم قابل تغییر اندازه نمی‌باشد. از توابع resize behavior و resize برای کنترل سایزو اندازه کروموزوم استفاده کنید.رفتار پیش فرض سایز ثابتی می‌باشد. با استفاده از متد resize behavior شما می‌توانید مقادیر مینیمم و ماکسیمم را برای اندازه کروموزوم مشخص کنید. اگر شما مقدار مینیمم و ماکسیمم را به صورت مقدار مساوی تعیین کنید، در این صورت، اندازه سایر ثابت به دست می‌آید. اگر شما از resize برای تعیین یک سایزی که بیرون از محدوده می باشد می‌خواهید اسفتاده کنید. اول از resize behavior در این صورت مرزها برای سازگاری با مقدار معین شما برای دوباره اندازه شدن عریض‌تر خواهد شد. و بالعکس و اگر مقادیری که شما توسط resizebehavir تعیین کرده‌اید با سایز کروموزوم جاری برخورد داشته باشد، کروموزوم دوباره اندازه می‌شود تا با مقادیر جدید هماهنگ باشد.
وقتی که resize behavior با هیچ آرگومان فراخوانی نشود، مقدار ماکسیمم سایز برگشت داده می‌شود. اگر کروموزوم قابل دوباره سایز شدن مجدد است، و یا GAGenome::fixed _ size اگر سایز و اندازه آن ثابت باشد.
تابع swap:
عناصر مورد نظر را جابجا می‌کند.
عملگرهای ژنتیکی برای این کلاس
|
فهرست مطالب
|
|
|
عنوان |
صفحه |
|
چکیده |
1 |
|
مقدمه |
2 |
|
الگوریتم ژنتیک |
5 |
|
تعریف خروجی(نمایش) |
8 |
|
عملگرهای مجموعه ژن |
10 |
|
شئ جمعیت |
13 |
|
توابع شئ و مقیاس گذاری مناسب |
14 |
|
نمایش الگوریتم ژنتیک درc++ |
15 |
|
توانایی عملگرها |
17 |
|
چگونگی تعریف عملگرها |
18 |
|
چگونگی تعریف کلاس مجموعه ژن |
22 |
|
سلسله مراتب کلاس ها |
23 |
|
1. سلسله مراتب کلاس GALib – گرافیکی |
23 |
|
2. سلسله مراتب کلاس GALib – مراتب |
24 |
|
رابط برنامه نویسی |
25 |
|
نام پارامترها و گزینه های خط فرمان |
26 |
|
رفع خطا |
28 |
|
توابع اعداد تصادفی |
29 |
|
GAGeneticAlgorithm |
31 |
|
GADemeGA |
42 |
|
GAIncrementalGA |
44 |
|
GASimpleGA |
47 |
|
GASteadyStateGA |
50 |
|
Terminators |
52 |
|
Replacement Schemes |
54 |
|
GAGenome |
55 |
|
GA1DArrayGenome<T> |
62 |
|
GA1DArrayAlleleGenome<T> |
65 |
|
GA2DArrayGenome<T> |
67 |
|
GA2DArrayAlleleGenome<T> |
70 |
|
GA3DArrayGenome<T> |
72 |
|
GA3DArrayAlleleGenome<T> |
76 |
|
GA1DBinaryStringGenome |
78 |
|
GA2DBinaryStringGenome |
81 |
|
GA3DBinaryStringGenome |
85 |
|
GABin2DecGenome |
88 |
|
GAListGenome<T> |
91 |
|
GARealGenome |
92 |
|
GAStringGenome |
94 |
|
GATreeGenome<T> |
96 |
|
GAEvalData |
97 |
|
GABin2DecPhenotype |
98 |
|
GAAlleleSet<T> |
100 |
|
GAAlleleSetArray<T> |
103 |
|
GAParameter and GAParameterList |
104 |
|
GAStatistics |
108 |
|
GAPopulation |
113 |
|
GAScalingScheme |
123 |
|
GASelectionScheme |
127 |
|
GAArray<T> |
130 |
|
GABinaryString |
132 |
|
نتیجه گیری |
135 |
|
مراجع |
136 |
|
فهرست مطالب
|
|
|
عنوان |
صفحه |
|
چکیده |
1 |
|
مقدمه |
2 |
|
الگوریتم ژنتیک |
5 |
|
تعریف خروجی(نمایش) |
8 |
|
عملگرهای مجموعه ژن |
10 |
|
شئ جمعیت |
13 |
|
توابع شئ و مقیاس گذاری مناسب |
14 |
|
نمایش الگوریتم ژنتیک درc++ |
15 |
|
توانایی عملگرها |
17 |
|
چگونگی تعریف عملگرها |
18 |
|
چگونگی تعریف کلاس مجموعه ژن |
22 |
|
سلسله مراتب کلاس ها |
23 |
|
1. سلسله مراتب کلاس GALib – گرافیکی |
23 |
|
2. سلسله مراتب کلاس GALib – مراتب |
24 |
|
رابط برنامه نویسی |
25 |
|
نام پارامترها و گزینه های خط فرمان |
26 |
|
رفع خطا |
28 |
|
توابع اعداد تصادفی |
29 |
|
GAGeneticAlgorithm |
31 |
|
GADemeGA |
42 |
|
GAIncrementalGA |
44 |
|
GASimpleGA |
47 |
|
GASteadyStateGA |
50 |
|
Terminators |
52 |
|
Replacement Schemes |
54 |
|
GAGenome |
55 |
|
GA1DArrayGenome<T> |
62 |
|
GA1DArrayAlleleGenome<T> |
65 |
|
GA2DArrayGenome<T> |
67 |
|
GA2DArrayAlleleGenome<T> |
70 |
|
GA3DArrayGenome<T> |
72 |
|
GA3DArrayAlleleGenome<T> |
76 |
|
GA1DBinaryStringGenome |
78 |
|
GA2DBinaryStringGenome |
81 |
|
GA3DBinaryStringGenome |
85 |
|
GABin2DecGenome |
88 |
|
GAListGenome<T> |
91 |
|
GARealGenome |
92 |
|
GAStringGenome |
94 |
|
GATreeGenome<T> |
96 |
|
GAEvalData |
97 |
|
GABin2DecPhenotype |
98 |
|
GAAlleleSet<T> |
100 |
|
GAAlleleSetArray<T> |
103 |
|
GAParameter and GAParameterList |
104 |
|
GAStatistics |
108 |
|
GAPopulation |
113 |
|
GAScalingScheme |
123 |
|
GASelectionScheme |
127 |
|
GAArray<T> |
130 |
|
GABinaryString |
132 |
|
نتیجه گیری |
135 |
|
مراجع |
136 |
