معرفی الگوریتم ژنتیک

[whitehat]

با توجه به اینکه سوال در موزد این الگوریتم زیاد شده کمی در مورد این الگوریتم در این تاپیک بحث می کنیم ، و به تدریج بحثهای قبلی را با این تاپیک ادغام خواهم کرد. عمده مطالب از دو مرجع زیر انتخاب شده اند :
سهراب امینی ، بهینه سازی ماشینهای DC مغناطیس دائم با جاروبک با استفاده از روشهای هوشمند ; دانشگاه صنعتی شریف، دانشکده برق ، پائیز 1377
رضا کیانی نژاد . جستاری در الگوریتم ژنی ; سمینار کارشناسی ارشد , دانشگاه تربیت مدرس , دانشکده مهندسی , گروه برق , قدرت 1 , پائیز 1373 .
-------------------------------
معرفی الگوریتم ها ژنتیک
الگوریتم ژنتیک، الگوریتم مبتنی بر تکرار است و اصول اولیه آن از علم ژنتیک اقتباس گردیده است. این الگوریتم که با تقلید از تعدادی فرایندهای مشاهده شده در تکامل طبیعی اختراع شده است، به طور مؤثری از دانش قدیمی موجود در یک جمعیت استفاده می کند، تا حل‏های جدید و بهبود یافته ایجاد کند. این الگوریتم در مسائل متنوعی نظیر بهینه سازی، شناسایی و کنترل سیستم، پردازش تصویر و مسائل ترکیبی، تعیین توپولوژی و آموزش شبکه‏های عصبی مصنوعی و سیستم های مبتنی بر تصمیم و قاعده به کار می‏رود. الگوریتم ژنتیک به دلیل تقلید نمودن از طبیعت دارای چند اختلاف اساسی با روش‏های جستجوی مرسوم می‏باشد که در زیر به تعدادی از آنها اشاره می‏کنیم:
1-الگوریتم ژنتیک با رشته‏های بیتی کار می‏کند که هر کدام از این رشته‏ها کل مجموعه متغیر‏ها را نشان می‏دهد. حال آنکه بیشتر روش‏ها به طور مستقل با متغیرهای ویژه برخورد می‏کنند.

2-الگوریتم ژنتیک در هر تکرار چند نقطه از فضای جستجو را در نظر می‏گیرد.

3-الگوریتم ژنتیک برای راهنمایی جهت جستجو، انتخاب تصادفی انجام می‏دهد که به این ترتیب اطلاعات مشتق نیاز ندارد. مکانیسم‏هایی که تکامل روی موجود زنده را انجام می‏شوند تا کنون به طور کامل فهمیده نشده‏اند. اما تعدادی از ویژگی‏های این مکانیسم شناخته شده است.

در اینجا تعدادی از ویژگی‏های یکی از تئوری‏های بسیار پذیرفته شده است آورده می‏شود.
1- تکامل، فرایندی است که روی رشته‏ها صورت می‏گیرد، نه روی موجود زنده‏ای که معرف آن رشته است.
2- انتخاب طبیعی، پیوندی ما بین رشته‏های و عملکرد ساختمان‏های رمز‏گشایی شده آنها می‏باشد.
3- فرایند تولید مثل، نقطه‏ای است که تکامل صورت می‏گیرد. تکامل ممکن است سبب شود که فرزند بیولوژیکی با والدین خود متفاوت می‏باشد.

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

در ادامه به اصطلاحات موجود در این الگوریتم ها می پردازیم

[whitehat]

اصطلاحالت الگوریتم ژنتیک
1- رشته ( کروموزوم) : آرایه‏ای از اعداد صحیح است که مقادیر عناصر این آرایه با توجه به نوع رشته تعیین می‏شود. مثلاً در رشته بیتی این عناصر فقط صفر و یک می توانند باشند. این رشته‏ها مشخص کننده مجموعه متغیر های بهینه سازی مسأله مورد نظر هستند.
2- ژن : بخشی از رشته که خصوصیات ویژه‏ای را معین می‏کند.
3- نماد ژنی : به ترکیب ژنتیکی یا همان رشته گفته می‏شود.
4- نماد معرف : به خصوصیات قابل مشاهده یک جاندار گفته می‏شود و در مسائل بهینه سازی به بردار حقیقی حاصل از رمز‏گشایی یک رشته گفته می‏شود.
5- نسل : یک دوره از زاد و ولد اعضاء یک جمعیت را یک نسل می‏گویند. به عبارت دیگر هر جایگزینی از جمعیت قدیمی به وسیله جمعیت جدید یک نسل ( زاد و ولد ) نامیده می‏شود.
6- شایستگی : در طبیعت به مقدار سازگاری و تطابق یک جاندار با محیط گفته می‏شود و در بهینه‏سازی به مقدار ارزیابی تابع هدف یا مقداری متناظر با آن به ازای یک رشته خاص، گفته می‏شود که نشان دهنده میزان مطلوب بودن آن رشته برای آن مسأله خاص ( تابع هدف ) می‏باشد.
7- تبادل ژنی : به جا به جایی و مبادله قسمت‏های متناظر از دو رشته گفته می‏شود.
8- جهش : به تغییر تصادفی و ناگهانی یکی از عناصر در یک رشته گفته می‏شود.

[whitehat]

در حالت کلی هر الگوریتم ژنتیک دارای سه جزء اساسی زیر است:
1- جزء ارزیابی 2- جزء جمعیت 3- جزء تولید مثل
---------------------------------------------------------------
1- جزء ارزیابی : شامل یک تابع ارزیابی است که درستی هر رشته‏ای که در جمعیت وجود دارد را اندازه گیری می‏کند. در مورد این جزء نکته مهم این است که چیز مخصوصی درباره تابع ارزیابی، که آن را با الگوریتم ژنتیک گره بزند، وجود ندارد و به راحتی می‏توان هر تابع دیگری را به جای آن تابع به کار برد. البته مادامی که تعداد متغییرهای دو تابع و محدوده تغییرات متغییر‏ها و دقت مورد نیاز آنها یکسان باشند. به عبارت دیگر، در الگوریتم ژنتیک هیچ اطلاعاتی درباره مسأله‏ای که باید حل شود، وجود ندارد و تا آنجایی که به الگوریتم ژنتیک مربوط می‏شود، صرفاً تولید مثل می‏کند و رشته‎های جدید تولید می‏کند و روی رشته‏های بیتی تولید شده به گونه‏ای عمل می‏کند که آنهایی که دارای ارزیابی بالاتری هستند، بیشتر اوقات تولید مثل کنند. فرایند رمز گشایی و تابع ارزیابی به راحتی می‏توانند جایگزین شوند. این تغییرات، تا مادامی که تعداد بیت‏های رشته‏ها ثابت بماند به تغییر اجزای دیگر الگوریتم ژنتیک نیاز ندارد.
2- جزء جمعیت : شامل جمعیتی از رشته‏ها و تکنیک‏هاست که این تکنیک‏ها برای ایجاد و دستکاری آن جمعیت استفاده می شود.
3- جزء تولید مثل : شامل روش هایی برای ایجاد رشته‏های جدید طی تولید مثل است.
تداخل بین سه جزء یک الگوریتم ژنتیک موقعی که در حال اجراست، به این صورت می‏باشد که جزء جمعیت از جزء تولید مثل، جمعیت جدید را می‏خواهد. جزء تولید از جزء جمعیت، والدینی که باید در رخداد تولید مثل به کار برده شوند را طلب می‏کند. در هر رخداد تولید مثل، دو والد از جزء جمعیت گرفته شده و روی آنها عملگرهای تبادل و جهش اعمال می‏شود تا دو فرزند تولید شود. همچنین موقعی که یک مجموعه جدید از فرزندان تولید شدند، جزء جمعیت از جزء ارزیابی برای ارزیابی فرزندان جدید ( رشته‏های جدید ) استفاده می‏کند.

[whitehat]

یک تشریح کلی از الگوریتم ژنتیک را می‏توان به صورت زیر در نظر گرفت :
1- جمعیتی از رشته‏ها را به صورت تصادفی بسازید.
2- هر رشته داخل جمعیت را ارزیابی کنید.
3- رشته‏های جدید را با ترکیب رشته‏های جاری ایجاد کنید. برای ترکیب رشته‎های والد از عملگر‏های جهش و تبادل استفاده کنید.
4- اعضایی از جمعیت را برای ایجاد فضایی برای رشته‏های جدید حذف کنید.
5- رشته‏های جدید را ارزیابی نموده و آنها را داخل جمعیت قرار دهید.
6- اگر زمان اجرا تمام شده است توقف نمایید و بهترین رشته را باز گردانید. در غیر این صورت به مرحله سه بازگردید.
روند ذکر شده در بالا متداول‏ترین روش الگوریتم ژنتیک را تشریح می‏کند. اما محققین مختلف، آن را به روش‏های متفاوت پیاده سازی کرده‎اند.
(دو روش متداول دیگر برای اختتام: همگرا شدن الگوریتم، تولید تعداد خاص نسل می‏باشد )

[whitehat]

اغلب نام الگوریتم ژنتیک متداول در مقابل الگوریتم ژنتیک ترکیبی آورده می‏شود. در الگوریتم ژنتیک متداول معمولاً از سه عملگر انتخاب، تبادل و جهش استفاده می‏شود. این سه عملگر معمولاً عملگرهای اساسی همه روش‏های الگوریتم ژنتیک هستند که از رشته‏های بیتی استفاده می‏کنند. با توجه به اینکه روش رمز کنندگی با استفاده از رشته‏های بیتی می‏توان با طیف وسیعی از مسائل روبرو شد؛ می توان گفت این سه عملگر و روش رمزکنندگی رشته بیتی باعث مقاوم شدن الگوریتم ژنتیک خواهد شد که در این مورد در بخش بعد توضیحات بیشتری داده خواهد شد.

1- عملگر انتخاب
هدف از انتخاب والدین در الگوریتم ژنتیک دادن شانس تولید مثل بیشتر به آن اعضایی است که برازندگی بالاتری داشته باشند. چندین روش برای انجام این کار وجود دارد.
یک روش که به طور معمول استفاده می‏شود، روش انتخاب با استفاده از چرخ گردان است. روند اجرای این روش به صورت زیر می‏باشد:
الف – برازندگی همه اعضای جمعیت را جمع کنید و نتیجه را برازندگی کل بنامید
ب- عدد n را به صورت تصادفی تولید کنید، به طوری که آن عددی بین صفر و برازندگی کل باشد. ج- اولین عضو از جمعیت را که برازندگی آن به اضافه برازندگی اعضای پیشین جمعیت بزرگ‏تر یا مساوی n باشد را باز‏گردانید.

اثر انتخاب والدین به روش چرخ گردان بازگردان یک والد می‏باشد که به صورت تصادفی انتخاب شده است. اگر چه این فرایند انتخاب، تصادفی است، شانس هر والدی که انتخاب می‏شود مستقیماً متناسب با برازندگی آن است. به طور متعادل در روی تعدادی از نسل‏ها این الگوریتم ژنتیک اعضای با کمترین برازندگی را دفع می‏کند و به انتشار مواد ژنتیکی در برازنده‎ترین اعضای جمعیت کمک می‏کند. البته ممکن است بدترین عضو جمعیت بتواند به وسیله این الگوریتم انتخاب شود ( زیرا به هر حال در روند این الگوریتم عنصر تصادف نیز وجود دارد. ) اتفاقاتی از این دست در جمعیتی با هر اندازه، قابل صرف‎نظر هستند و به فرض انتخاب چنین اعضایی در یک نسل، احتمال دفع آنها در نسل‏های بعدی بسیار بیشتر است. به هر حال، با گذشت چند نسل، این اعضا از جمعیت دفع می‏شوند. در به کار بردن روش انتخاب والدین باید دقت شود که مقادیر برازندگی رشته‏ها باید اعداد مثبت باشند.

2- عملگر تبادل
عملکرد این عملگر و عملگر جهش باعث می‏شود که رشته های تولید شده طی تولید مثل، از رشته‏های والدینشان متفاوت باشند. در طبیعت، این عملگر موقعی رخ می‏دهد که دو والد قسمت‏هایی از رشته‏های متناظرشان را معاوضه کنند و در الگوریتم ژنتیک، عملگر تبادل، مواد ژنتیکی دو رشته والد را مبادله می‏کند تا دو فرزند ( رشته جدید ) ایجاد شود. چندین نوع عملگر تبادل وجود دارد. ولی معروف‏ترین عملگر تبادل به کار رفته در الگوریتم ژنتیک عملگر یک نقطه‏ای می‏باشد.
در الگوریتم ژنتیک این عملگر به صورتی که در زیر تشریح می‏شود، اعمال می‏گردد. برای اینکه بتوانیم از این عملگر استفاده کینم نیاز به دو رشته داریم. بنابراین با دوبار اعمال عملگر انتخاب روی جمعیت جاری دو رشته از آن را انتخاب می‏کنیم سپس یک آزمون احتمال انجام می‏دهیم تا مشخص شود که عملگر تبادل روی دو رشته اعمال بشود یا نشود. این آزمون با استفاده از یک سکه نا همگن صورت می‏گیرد به این صورت که سکه با احتمال (Pcross) شیر و با احتمال (1- Pcross) خط می‏آید. به عنوان مثال، اگر قرار باشد با شیر آمدن سکه عملگر تبادل بر روی رشته اعمال گردد، فرض می‏کنیم سکه را پرتاب کرده‏ایم و شیر آمده است. سپس وارد مرحله بعدی یعنی اجرای عملگر تبادل می‏شویم یک عدد تصادفی بین یک و طول رشته‏ تولید می‏شود.پس از مشخص شدن این عدد صحیح که نشان دهنده مکان تبادل روی رشته‏ها است, هر دو رشته از محلی که این عدد مشخص می‏کند شکسته می‏شوند و قسمت‏های انتهایی آنها با همدیگر معاوضه می‏شوند. اکنون قسمت‏های جدا شده به همدیگر متصل می‏شوند، تا دو رشته جدید حاصل شود



3-عملگر جهش
این عملگر نیز یکی از عملگرهای الگوریتم ژنتیک است و به کارگیری آن قابلیت الگوریتم ژنتیک را برای یافتن حل‏های نزدیک بهینه افزایش می‏دهد. جهش، تغییر اتفاقی در مقدار یک وضعیت ویژه رشته می‏باشد. با به کارگیری این عملگر مشخصه هایی که در جمعیت والدین وجود ندارد، ایجاد می‏شود. زیرا جهش باعث تغییر مقدار یک ژن می‏شود یعنی اگر یک باشد صفر می‏شود و بالعکس اگر صفر باشد یک می‏شود. لذا همین موضوع باعث تغییر مشخصه‏های یک رشته می‏شود و برای اینکه جمعیت پیش از موعد همگرا نشود، مناسب می‏باشد. زیرا یکی از دلایل همگرایی پیش از موعد یکسان بودن اعضاء جمعیت می باشد که عملگر جهش باعث می شود احتمال یکسان شدن اعضاء در جمعیت های جدید بسیار کاهش یابد. روش پیاده سازی این عملگر در زیر توضیح داده می شود.
این عملگر بر خلاف عملگر تبادل که به دو رشته نیاز داشت، به یک رشته نیاز دارد، پس از اینکه عملگر تبادل روی دو رشته اعمال شد و دو رشته جدید به دست آمد، عملگر جهش به این دو رشته به صورت مجزا اعمال می شود. روش اعمال به این صورت است که برای تک تک عناصر یک رشته، آزمون احتمال جهش صورت می‏گیرد. در صورتی که این آزمون با موفقیت انجام شود، مقدار آن وضعیت از یک به صفر یا از صفر به یک تغییر می‏کند و به اصطلاح جهش می‏کند. انجام آزمون احتمال نیز با استفاده از یک سکه نا همگن که با احتمال (Pcross) شیر و با احتمال (1- Pcross) خط می‏آید، صورت می‎گیرد و در صورتی که با پرتاب سکه شیر آمده باشد مقدار بیت مربوط جهش می‏کند.
همانطور که در بالا گفته شد بایستی آزمون احتمال برای تک تک وضعیت‎های یک رشته صورت گیرد. به عبارت دیگر برای هر جهش یک بار سکه ناهمگن رها می‏شود و با توجه به نتیجه، مقدار بیت جهش می‏یابد یا جهش نمی‏یابد.

[whitehat]

در این قسمت نکاتی درباره پیاده‎سازی الگوریتم ژنتیک دودوئی مانند تشکیل رشته‎ها، تعداد بیت‎های متناظر با هر متغییر، رمزگشائی، انواع روش‎های تشکیل رشته، تعداد بیتهای متناظر با هر متغییر و چگونگی تشکیل رشته‎ها توضیح داده می‎شود. به دلیل وجود فرمول از pdf استفاده شده

[Alireza_Salehi]

خیلی ممنون

پیشنهاد:
1. بهتر بود معادل انگلیسی کلمات کلیدی متن (عناوین) را به صورت زیر نویس قرار می داید.
2. این کتاب خیلی زیبا ، روان و کاربردی الگوریتم ژنتیک را تشریح کرده:
Genetic Algorithms and Engineering Design (http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471127418.html)

[hasankhaksar]

سلام. موضوع پایان نامه من بهینه سازی شبکه اتوبوسرانی شهری با استفاده از ژنتیکه. آیا کسی هست که برنامه نویسی و کدینگ ژنتیک رو بدونه و بتونه کمکم کنه؟؟

[meytim]

براي الگوريتم ژنتيك زيربخش آخر از آخرين بخش كتاب "شگردهاي عددي" رو هم مي‏تونيد بخونيد. موقعي كه من اون كتاب رو نوشتم، هنوز شركت MathWorks جعبه‏ابزار الگوريتم ژنتيك رو ارائه نداده بود، واسه همين برنامه‏ها رو خودم نوشتم. برنامه‏هاي كتاب رو مي‏تونيد از لينك زير دانلود كنيد.


http://mmnrecipes.blogspot.com (http://mmnrecipes.blogspot.com/)


زيربخش آخر از بخش آخر كتاب من در مورد الگوريتم ژنتيك هست. احتمالاً اولين كتاب فارسي در مورد الگوريتم ژنتيك همين است كه من نوشته‏ام (سال 1381). آن موقع شركت MathWorks هنوز Toolbox براي الگوريتم ژنتيك نداده بود، براي همين برنامه‏هاي الگوريتم ژنتيك آن كتاب را خودم نوشتم، و مطمئناً ساده‏تر از آني هست كه شركت MathWorks داده؛ اين طبيعي است، چون يك نفر كجا و يك تيم كجا؟ اما در هر صورت مفاهيم آن را داخل كتاب توضيح دادم و برنامه‏هايش هم قبل از اينكه كتاب رو چاپ كنم حداقل براي 20 تا پروژة ليسانس و فوق ليسانس تست شده. به نظر من پيش‏نياز نمي‏خواد، چون مفاهيمش خيلي ساده هست. البته بعضيها يك سري مفاهيم پيچيده رو به هر مبحثي اضافه مي‏كنن؛ من اين كار رو نكردم. فقط بايد متلب بلد باشيد، كه اون رو هم در بخش اول كتاب به طور خلاصه گفتم.

[afabahar]

باز هم کارتون عالی بود.
به زودی نتیجه این تحقیقاتم رو در زمینه الگوریتم ژنتیک در اختیار سایرین قرار میدهم.
با تشکر

[majidshe]

با الگوریتم ژنتیک مسئله 8 وزیر را در متلب و ی شارپ لازم دارم لطفا کمک کنید

[mjal146]

اگر ممکنه یه مثال خیلی ساده از الگوریتم ژنتیک بزنید (فروشنده و 8وزیر و مینیمم تابع نباشد) مثلا حل معادله درجه 2 با کدش به زبان سی یا سی پلاس پلاس:قلب:
خیلی لازم دارم:افسرده:

[mjal146]

با الگوریتم ژنتیک مسئله 8 وزیر را در متلب و ی شارپ لازم دارم لطفا کمک کنید




آموزش پیاده سازی گرافیکی هشت وزیر با C#


گام نخست : پیاده سازی مهره و کاشی بازی







مهره نشان دهنده وزیر








را ایجاد کنید.eight_queen ای به نام Windows Application برنامه Visual C# را اجرا کنید و از قسمت Visual Studio


SquareControl.cs به نام User Control یک Add new item بر روی پروژه یتان کلیک راست کنید و از قسمت


کاشی صفحه شطرنج ما را می سازدUser control را ایجاد کنید.در واقع این


این کنترل را به 32, 32 تغییر می دهیم.حالا کاشی تخته یمان آماده شد!size


تخته یمان که به شکل دایره است می رسد(Discs)نوبت به طراحی مهره های


این مهره ها را می توان به 2 صورت پیاده سازی کرد:


با قرار دادن عکس وزیر درون کاشی های شطرنج .1


با کشیدن دایره درون کاشی های شطرنج. .2


که در این مقاله راه دوم را برگزیدیم.یعنی با کد زیر دایره ای با رنگ سفید یا سیاه درون کاشی هایمان رسم می کنیم.



e.Graphics.DrawEllipse(SquareControl.pen, left, top, width, height);


را حذف کردیم و آنرا به گام های بعدی محول کرده ایم.shadow و animationدر این گام ما قسمت



گام دوم : تعریف پارامترها و نام دامنه برای User Control ها








نام دامنه




پارامتر






اضافه می کنیم:User controlدر ابتدای کار نام دامنه زیر را


using System.Drawing.Drawing2D;


سپس رنگ کاشی خود را تعیین می کنیم:


public static Color NormalBackColor= Color.Green;


باید متغیری برای ذخیره کردن ردیف و ستون مهره ها ایجاد کنیم.به این دلیل که کدمان حرفه ای تر بشود ، آنها را تعریف کرده ایم:propertyمستقیمان به صورت


// These reflect the position of the square on the board.
Public int col{get;set;}
public int row{get;set;}


در انتها هم رنگ و قلم موی خود را انتخاب می کنیم:


// Drawing tools.
Private static Pen pen = new Pen(Color.Black);
private static SolidBrush solidBrush = new SolidBrush(Color.Black);




























گام سوم : تابع تنظیم ردیف و ستون









ما در این گام باید تابعی را بسازیم که بتوانیم از بیرون از این کلاس، ردیف و ستون مهره هایمان را تنظیم کنیم.


در گام پیشین تعریف propertyبا این کار ما میتوانیم وضعیت ردیف و ستون مهره هایمان را که به صورت


کردیم را دریافت کنیم و پس از محاسبه حرکت صحیح توسط هوش مصنوعی برنامه یمان بوسیله ی این تابع


از دوباره ردیف و ستون مهره هایمان را مقدار دهی کنیم.


Public SquareControl(int row, int col)
{
// This call is required by the Windows.Forms Form Designer.
InitializeComponent();
this.Contents = Board.Empty;
this.row = row;
this.col = col;
// Prevent the control from receiving focus via the TAB key.
This.TabStop = false;
// Set the background color.
This.BackColor = SquareControl.NormalBackColor;
}






گام چهارم : ایجاد و نابود سازی User Control ها

ن مقاله موزیرود در محیط های مختلف طراحی و پیاده سازی کنند.گوریتم هشت وزیر را تحلیل کرده و بازگشتی و غیر بازگشتی نوشته






انحدام




ایجاد





InitializeComponent()تابعی ای که شاید در گام قبل برای برخی ها نا آشنا به نظر برسد تابع


ما را می سازد. و در بطن کد نویسی ما دخالتیuser controlمی باشد.این تابع در واقع اجزای اصلی


ندارد:


private void InitializeComponent()
{
// SquareControl
this.Name = “SquareControl”;
this.Size = new System.Drawing.Size(32, 32);
this.Paint += new System.Windows.Forms.PaintEventHandler(this.Square Control_Paint);
}



می باشد.همانگونه که می دانید دات نت دارای خواصیتی به نامuser controlتابع بعدی ما برای نابود سازی


خود خارج می شود.scoop می باشد .به این معنا است که هنگامی که کنترل ما از Garbage collector


دات نت بصورت خودکار آن شئی را نابود می کند.این خواصیت دات نت باعث بهبود عملکرد برنامه می شود.


Protected override void Dispose( bool disposing )
{
if( disposing )
{
if(components != null)
{
components.Dispose();
}
}
base.Dispose( disposing );
}


بصورت خودکار توسط ویژاوال استدیوdispose و InitializeComponent تابع


ایجاد می شود،بنابرین نیاز به حفظ کردن و توضیحات در این باره نمی باشد.


فقط نکته ای که در این بین هست، ما برای سحولت و داکیومنت کردن این پروژه


SquareControl.cs در قسمت SquareControl.Designer.csآنرا از قسمت


نوشته ایم.به این دلیل که هر دوی آنها درون یک کلاس می باشند.در کد نویسی


آن تفاوتی بوجود نمی آید.













گام پنجم : چیدن مهره ها در صفحه شطرنج








حالا به مهم ترین قسمت طراحیمان که همان طراحی مهره ها می باشد میرسیم.در این مرحله ما باید هر دفعه که


ما فراخوانی می شود، مهرهایمان ها را بچینیم.


می باشد. SquareControl_Paint ای که می توانیم برای اینکار فراخوانی کنیم،eventبهترین


ما فراخوانی میشود. کد های درونUser controlحالا با قرار دادن کدهایمان درون این تابع هربار که


آن اجرا می شود.


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


// Set drawing options.
e.Graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;



حالا ما با دستور شرطی حالتی را میسنجیم که در صورت برقرار بودن هر یک از 2 شرط زیر دستور مربوطه اجرا شود:

1. کاشی ما در حال حاضر دارای هیچ مهر ای نباشد
2. محتویات جدید کاشی ما مهره سیاه باشد.

if (this.Contents != Board.Empty)



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


رسم میکنیم:


e.Graphics.FillEllipse(SquareControl.solidBrush, left, top, width, height);


) مهره هایمان روی کاشی از کد زیر استفاده می کنیمpositionخوب،برای تعیین مکان (


// Get size and position parameters based on the control size.
Int size = (int) (this.Width * (0.80));
int offset = (int) ((this.Width – size) / 2);
int thickness = (int) (size * 0.08);
int width = size;
int height = size;
int left = offset;
int top = offset + (int) Math.Round((double) (size – height) / 2.0);



حالا درون شرط بالا، شرط دیگری را اضافه میکنیم.در این شرط بررسی می کنیم که آیا


کاشی قبلی خالی بوده است یا خیر.این شرط را به این دلیل بررسی می کنیم که


اگر مهره ای قرار نگرفته بود آنرا بسازیم.


If (this.PreviewContents == Board.Empty)
{


SquareControl.solidBrush.Color = Color.Black;
else
{


}
e.Graphics.FillEllipse(SquareControl.solidBrush, left, top, width, height);
}

[mjal146]

گام ششم : کشیدن حاشیه بین کاشی ها.باشد.




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


// Draw the border.


Point topLeft = new Point(0, 0);


Point topRight = new Point(this.Width – 1, 0);


Point bottomLeft = new Point(0, this.Height – 1);


Point bottomRight = new Point(this.Width - 1, this.Height - 1);


SquareControl.pen.Color = Color.Moccasin;


SquareControl.pen.Width = 1;


e.Graphics.DrawLine(SquareControl.pen, bottomLeft, topLeft);


e.Graphics.DrawLine(SquareControl.pen, topLeft, topRight);


SquareControl.pen.Color = Color.Navy;


e.Graphics.DrawLine(SquareControl.pen, bottomLeft, bottomRight);


e.Graphics.DrawLine(SquareControl.pen, bottomRight, topRight);
















گام هفتم : نگاه کلی بر کلاس SquareControl





















فصل دوم : پیاده سازی محیط بازی



گام هشتم : تعریف متغییر های تخته بازی






تخته بازی




<-متغییر ها در



در پیاده سازی بازی هشت وزیر از متغییر های زیر استفاده شده است :
private Board board;

private eightQueen queen;
private Boolean[, ,] memory;
private Int32 moveNumber;
در اینجا کلاس eighteQueen در واقع نشان دهنده کلاسی است که الگوریتم بازی در آن نوشته شده است.
آرایه سه بعدی memory هم نشان دهنده مکان 8 وزیر در 92 حالت ممکن است.اندیس اول و دوم این آرایه مختص ردیف و ستون بازی می باشد و اندیس سوم این آرایه برای نگه داری 92 حالت ممکن بازی می باشد.این آرایه به صورت Boolean نمایش داده شده است.به این معنا که محتویات این ارایه می تواند True یا False باشد.در صورتی که مهره ای درون صفحه نباشد،مقدار این متغییر False میشود و در صورتی که بر اساس الگوریتم،مهره وزیری در این مکان وجود داشته باشد،مقدار این متغییر True می شود.
متغییر سراسری moveNumber هم در واقع اندیس سوم آرایه memory می باشد.در بازی شما می توانید با کلیک کردن بر روی دکمه next و previous می توانید مقدار این متغییر را زیاد یا کم کنید.


























گام نهم : پیاده سازی تابع سازنده تخته بازی





در این متد ،ما با 2 حلقه for در 64 آرایه جستجو می کنیم،در صورت وجود وزیر در هر یک از خانه ها،آن را در خانه مرتبطش در صفحه شطرنج قرار می دهیم

private void UpdateBoardDisplay()
{


// Map the current game board to the square controls.
SquareControl squareControl;
for (int row = 0; row < 8; row++)
{
for (int col = 0; col < 8; col++)
{
squareControl = (SquareControl)this.squaresPanel.Controls[row * 8 + col];
if (memory[row, col, this.moveNumber] == true)
{



squareControl.Contents = 1;
}
else squareControl.Contents = 0;
}


}


// Redraw the board.


this.squaresPanel.Refresh();


}
در آخر هم صفحه ای که خانه های شطرنج در آنها وجود دارد،refresh می شود.با اینکار رنگ مناسب هر خانه در صفحه ترسیم می شود.



گام دهم : ذخیره 92 حالت مختلف




private void btnNext_Click(object sender, EventArgs e)
{
if (moveNumber < 93 && moveNumber > -1)
{
this.moveNumber++;
this.UpdateBoardDisplay();
}
else
MessageBox.Show("You are at end move");
}
همانطور که بسیار روشن است، ابتدا بررسی می کنیم که آیا شماره حرکت ما در دامنه مجاز وجود دارد یا خیر، سپس یک واحد به شمارنده حرکت اضافه می کنیم.و متد UpdateBoardDisplay برای نشان دادن،شماره حالت مورد نظر در الگوریتم هشت وزیر استفاده می کنیم.

private void btn_previous_Click(object sender, EventArgs e)
{
if (moveNumber < 93 && moveNumber > 0)
{
this.moveNumber--;
this.UpdateBoardDisplay();
}
else
MessageBox.Show("You are at firs move");


}

این متد هم عکس متد پیشین را انجام می دهد.















فصل سوم : الگوریتم هشت وزیر به روش غیر بازگشتی


گام یازدهم : معرفی الگوریتم


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



public Boolean[, ,] calculate()


{


board = new Boolean [8,8];


memory = new Boolean[8, 8, 92];




for ( int a = 0 ; a < 8 ; a++ )


if(test( 0 , a ))


for ( int b = 0 ; b < 8 ; b++ )


if(test( 1 , b ))


for ( int c = 0 ; c < 8 ; c++ )


if(test( 2 , c ))


for ( int d = 0 ; d < 8 ; d++ )


if(test( 3 , d ))


for ( int e = 0 ; e < 8 ; e++ )


if(test( 4 , e ))


for ( int f = 0 ; f < 8 ; f++ )


if(test( 5 , f ))


for ( int g = 0 ; g < 8 ; g++ )


if(test( 6 , g ))


for ( int h = 0 ; h < 8 ; h++ )


if (test(7, h))


{




for ( int m = 0 ; m < 8 ; m++ ) {


for (int n = 0; n < 8; n++)


memory[m, n, BoardNO] = board[m,n];


}


BoardNO++;


}




return memory;


}
















گام دوازدهم : روش بررسی صحّت قرار گیری مهره


همانگونه که می دانید ، حرکت مجاز برای وزیر، به صورت مورب و بعلاوه است،درست شبیه همان چیزی که در بازی Reversi دیده ایم . برای بررسی کردن 8 جهت هر وزیر ما باید با کم کردن و زیاد کردن ردیف و ستون ، آن را آزمایش کنیم :

Boolean test( int i , int j )
if ( board[i - b,j] != false )
if (board[i - b, j - b] != false)
if (board[i - b, j + b] != false)
به این دلیل که هنوز وزیر های ردیف های بعدی ساخته نشده اند]مراجعه شود به گام قبل[ردیف های بعدی را اعتبار سنجی نمی کنیم.در آخر کد زیر را داریم:
Boolean test( int i , int j )
{
for ( int a = 0 ; a < 8 ; a++ )
board[i, a] = false;
for ( int b = 1 ; b < 8 ; b++ )
if ( i - b >= 0 ) {
if ( board[i - b,j] != false )
return false;
if ( j - b >= 0 )
if (board[i - b, j - b] != false)
return false;
if ( j + b <= 7 )
if (board[i - b, j + b] != false)
return false ;
}
board[i,j]= true ;
return true ;
}











فصل چهارم : الگوریتم هشت وزیر به روش بازگشتی

گام سیزدهم : معرفی الگوریتم

همانگونه که می دانید استفاده از الگوریتم بازگشتی دارای مزیت بسیار بزرگی است ، و آن خوانایی ودرک راحت تر آن می باشد . از اینرو است که بیشتر برنامه نویسان از الگوریتم های بازگشتی برای حل مسائلاش استفاده می کنند..
در الگوریتم بازگشتی هشت وزیر که در زیر آورده شده است. روش محاسبه آن بصورت زیر می باشد.

/**
* Place a queen in a row and check its validity. If valid then place it in the
* next row else backtrack.
*
* @param row
*/
public void place(int row) {
if (row == 8) {

for (int r = 0; r< 8; r++)
{
for (int c = 0; c < 8; c++)
{
if (board[r] == c){
memory[r, c, number] = true;
// MessageBox.Show(r.ToString()+"/"+c.ToString()+"/"+number.ToString());
}else
memory[r, c, number] = false;
}

}
this.number++;
return;
} else {
for (int i = 0; i < 8; i++) {
board[row] = i;
if (valid(row)) place(row + 1);
}
}


}

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








گام چهاردهم : روش بررسی صحّت قرارگیری مهره

در این متد روشی جالب برای مجاز بودن حرکت استفاده شده است.
در این متد،اگر مقدار ردیف و ستون و یا مورب ردیف و ستون ردیف های پیشین وزیر یکسان بود،مقدار false را بر می گرداند،ردیف و ستون مفعلی و مورب مهره یکسان نبود،مقدار false را برمی گرداند.
/**
* Checks the validity of a position. If valid returns true else returns false.
*
* @param row
* @return
*/
public Boolean valid(int row) {
for (int i = 0; i < row; i++) {
if ((board[i] == board[row]) || Math.Abs(board[row] - board[i]) == (row - i)) {
return false;
}
}

return true;


}





منبع:


پروژه درس هوش مصنوعی




نوشته: شریفی