پرواز با بال ژنتيك در دنياي جداول سودوكو! - Artificial Intelligence

**Astaraki** · ۱۰-۲۳-۱۳۸۸, ۰۷:۰۴ بعد از ظهر

پرواز با بال ژنتيك در دنياي جداول سودوكو

1- صورت مسئله

احتمالا‌ً همه شما با جداول سودوكو (Sodocu) آشناييد، جداول بازي با اعدادي كه اكنون در اكثر روزنامه‌ها و مجله‌ها در قسمت سرگرمي فضايي را به خود اختصاص داده‌اند يا شايد در اطرافتان افرادي باشند كه به صورت جدي به حل مداوم اين‌گونه جداول مي‌پردازند، اما اگر اطلا‌عي از اين جداول و نحوه انجام اين بازي نداريد، در اينجا به اختصار برايتان توضيح مي‌دهم.

جدول سودوكو در حقيقت يك جدول 9*9 است كه بعضي از خانه‌هاي آن با اعدادي بين 1 تا 9 پرشده است. شما مي‌توانيد در هر خانه خالي يكي از اعداد 1 تا 9 را قرار دهيد اما بايد اين كار را طوري انجام دهيد كه سه شرط زير برقرار باشد.

1- در هر سطر هيچ عدد تكراري وجود نداشته باشد.
2- در هر ستون هيچ عدد تكراري نبايد وجود داشته باشد.
3- در هر جدول 3*3 طبق شكل نيز نبايد هيچ عدد تكراري وجود داشته باشد.

در جدول 1 يكي از جداول حل شده سودوكو را مي‌بينيد كه شروط مورد نظر در آن صادق است، اما در حقيقت شكل آغازين مسئله مانند جدول 2 است كه بايد حل شود. اگر به حل يك نمونه جدول سودوكو تمايل داريد، مي‌توانيد جدول 2 را حل كنيد.

مسئله‌اي كه مي‌خواهيم در اين مقاله حل كنيم بدين‌صورت است كه فرض كنيد يك جدول سودوكوي خالي داريد و از شما مي‌خواهند مثلا‌ً پنجاه راه‌حل معرفي كنيد. يعني به پنجاه جدول كه خاصيت سودوكو داشته باشد. توجه كنيد كه در مسئله ما همه خانه‌ها خالي هستند. براي اين‌كه زمان اجراي اين برنامه كمتر شود و امكان رسيدن به جواب در خانه نيز مهيا باشد، در صورت مسئله مورد نظر تغيير كوچكي داديم؛ فرض كنيد در هر خانه غير از اعداد 1 تا 9 عدد صفر را نيز مي‌توانيد قرار دهيد.

اگر بخواهيم بيان پيشرفته‌تري از صورت مسئله داشته باشيم، در حقيقت اين مسئله، پيدا كردنِ حالت‌هاي مناسبي است در بين همه حالا‌ت ممكن براي جدول مزبور ما. در هر خانه جدول ده عدد مختلف مي‌تواند قرار بگيرد. از طرفي داراي 81 خانه هستيم.

پس مقدار حالا‌ت ممكن براي مسئله ما برابر 1081 است و از ميان همه اين حالا‌ت ما مي‌خواهيم به دنبال حالت‌هايي بگرديم كه شرايط مورد نظر ما را داشته باشد. بديهي است پيمايش همه اين حالا‌ت، حتي براي كامپيوترهاي امروزي كه ما از آن‌ها استفاده مي‌كنيم و در مدت زمان طبيعي، امري محال است.

2- حل مسئله

با توجه به اين‌كه تعداد حالا‌ت مسئله بسيار زياد است، پيمايش كل فضاي درخت حالت مسئله غيرممكن است. از طرفي ما نيازمند پنجاه جواب درست هستيم و مطمئناً جواب‌هاي مسئله ما در فضاي درخت حالت مسئله پراكنده هستند و در نهايت اين شرايط اين ايده را به وجود مي‌آورد كه براي حل مسئله از الگوريتم‌هاي ژنتيك استفاده كنيم. اما براي پياده‌سازي برنامه سعي مي‌كنم همه مراحل را قدم به قدم توضيح دهم.

2-1- تعيين كروموزم

همان‌طور كه در مقاله قبلي ذكر شده بود، قدم اول تعيين ساختار كروموزم است. همان‌طور كه مي‌دانيم هر كروموزم در الگوريتم ژنتيك، معادل يك وضعيت از حالات ممكن براي فضاي حالت مسئله است.

در مسئله ما نيز جدول سودوكو را در قالب يك آرايه يك‌بعدي مي‌توانيم تصور كنيم كه اعداد متناظر با هر خانه به ترتيب در كنار هم قرار گرفته‌اند و در مراحل بعد با تعيين يك نقطه شكست در اين آرايه، مي‌توانيم عمل تركيب را براي به دست آوردن حالات جديد انجام دهيم، اما در همين ابتدا مي‌توانيم از اندكي ذكاوت برنامه‌نويسي خود استفاده كنيم و به جاي اين‌كه جدول سودوكو را يك آرايه يك بعدي با 81 خانه در نظر بگيريم، همان آرايه دو بعدي 9*9 در نظر بگيريم و فقط شكست را تركيبي از سطر و ستون فرض كنيم.

مثلا‌ً اگر دو كروموزم به شكل فرضي زير باشند، با اين فرض كه نقطه شكست در سطر بعد از ستون 1 باشد، حاصل تركيب به فرم شكل 1 خواهد بود. (براي واضح بودن شكل فرض كرديم هر جدول 4 *4 خانه است.)

2-2 - ساختن جمعيت آغازين يا نسل اول

کد 1

همان‌طور كه مي‌دانيم، جمعيت آغازين را مي‌توانيم به صورت تصادفي ايجاد كنيم. يعني در هر خانه از يك نمونه از جدول مورد نظر يك عدد تصادفي بين صفر تا نُه قرار دهيم. در اينجا ذكر چند نكته لا‌زم است: اول اين‌كه، در كد قرار گرفته در بخش دانلود سايت ماهنامه شبكه من تعداد كروموزم‌هاي جمعيت آغازين را برابر پنجاه فرض كردم و از اين به بعد از هر نسل پنجاه عنصر انتخاب مي‌شوند و به عنوان عناصر سازنده نسل بعدي مورد استفاده قرار مي‌گيرند.

از طرف ديگر، اگر بتوانيم جمعيت آغازين خود را به گونه‌اي انتخاب كنيم كه در عين تصادفي بودن قسمت‌هايي از شروط‌ها را نيز در خود داشته باشد، مطمئناً بسيار سريع‌تر به جواب مي‌رسيم؛ چراكه همان‌طور كه در مقاله قبل گفته بوديم، هر چه جمعيت آغازين بهتر باشد، احتمال دسترسي سريع به جواب بيشتر است.

کد 2

با توجه به اين ايده مي‌توانيم جمعيت آغازين را به‌گونه‌اي طراحي كنيم كه با اين‌كه در هر خانه يك عدد تصادفي قرار داشته باشد، در هر سطر هيچ عدد تكراري نداشته باشيم. (كد 2)

در اينجا ذكر يك نكته لازم است كه با توجه به اين‌كه نيازمند تعداد بسيار زيادي عدد بين 0 تا 9 به صورت تصادفي هستيم و با توجه به اين‌كه اين اعداد در كسر بسيار كوچكي از زمان براي كامپيوتر توليد مي‌شوند، نمي‌توانيم از توابعي مانند RND كه عدد تصادفي ايجاد مي‌كنند، استفاده كنيم؛ چراكه هسته يا سيد توليد عدد تصادفي در اين توابع در بهترين حالت ساعت (زمان) اجراي تابع است كه براي ما مناسب نيست.

به همين منظور، مي‌توانيم از RngCryptoServiceProvider از كلا‌س System.Security.Cryptography استفاده كنيم. (كد 1)

2-3- ساختن تابع از ارزش

در ادامه بايد تابعي ايجاد كنيم كه بتوانيم توسط آن به هر نمونه عددي متناسب با ميزان خوب بودن آن را اختصاص دهيم. اين تابع را كه RANK مي‌ناميم، بدين‌صورت تعريف مي‌كنيم: به ازاي هر سطر يا ستون يا هر مربع 3 *3 كه شرط جدول سودوكو را داشته باشد، يك واحد به جواب تابع RANK اضافه مي‌كنيم.

کد 3

بدين‌صورت تابع RANK تابعي خواهد بود كه داراي جواب بين صفر تا 27 ‌باشد. البته بديهي است كه اگر نمونه‌اي داراي RANK برابر 27 باشد، بدين معني است كه معادل يكي از المان‌هاي جواب نهايي سودوكو مسئله ما است. (كد 3)

بايد توجه داشت كه خروجي تابع RANK از نظر برنامه‌نويسي آرايه‌اي است يك‌بعدي به طول تعداد نمونه‌هايي كه قرار است ارزشيابي شوند. مثلا‌ً اگر بخواهيم جمعيت پنجاه‌گانه اوليه را ارزشيابي كنيم، خروجي تابع ما آرايه‌اي يك بعدي با طول پنجاه است كه ارزش نمونه صفر در خانه شماره صفر و به همين ترتيب تا ارزش نمونه 49 در خانه شماره 49 قرار مي‌گيرد. (كلا‌ً پنجاه نمونه). (در VB آرايه‌ها از شماره صفر آغاز مي‌شوند).

2-4- تركيب نمونه‌ها و ساختن جواب جديد

کد 4

در ادامه بايد هر بار دو نمونه را انتخاب كنيم و از تركيب هر دو نمونه دو جواب جديد به دست آورديم. اين عمل را در اين برنامه پنج هزار بار انجام داديم. يعني از تركيب تصادفي دو نمونه تصادفي از ميان پنجاه نمونه مزبور، ده هزار جواب جديد ايجاد كرديم.

بايد توجه داشت كه نبايد يك نمونه با خودش تركيب شود؛ چراكه دو جواب عيناً مثل خودش توليد مي‌كند. در نهايت اگر بخواهيم به طور خلا‌صه بيان كنيم، با انتخاب دو عدد تصادفي بين صفر تا 49 دو نمونه را انتخاب مي‌كنيم.

توجه داشته باشيد كه بايد اين عدد تصادفي به گونه‌اي باشد كه نمونه‌اي كه داراي مقدار تابع ارزش بيشتري است، به همان نسبت نيز داراي شانس انتخاب بيشتري باشد. براي اين كار، از تابعي به نام Selectinst استفاده كرديم كه حتماً در Source برنامه متن آن را خواهيد ديد. (كد 4)

پس از اين انتخاب دو نمونه با انتخاب دو عدد تصادفي بين صفر تا هشت شماره سطر و ستون نقطه شكست را به دست مي‌آوريم و عمل تركيب را انجام مي‌دهيم و دو جواب جديد به دست مي‌آوريم، اما صرف عمل تركيب ما را به جواب نهايي رهنمون نخواهد كرد، بلكه بايد از عمل جهش نيز استفاده كنيم.

کد 5

بنابراين به ازاي هر جواب به دست آمده است اين اعمال را انجام دهيم. ابتدا يك عدد تصادفي بين يك يا صفر انتخاب مي‌كنيم. اگر عدد ما صفر بود، عمل جهش را انجام نمي‌دهيم، اما اگر يك بود، دو عدد تصادفي ديگر بين صفر تا هشت به نشانه شماره سطر و ستون خانه‌اي كه بايد در آن جهش انجام شود و يك عدد تصادفي بين صفر تا نُه به عنوان مقدار جديد آن خانه به دست مي‌آوريم و عمل جهش را در آن انجام مي‌دهيم. بدين‌ترتيب هر جواب ممكن است با احتمال پنجاه درصد در يكي از ژن‌هاي خود دچار جهش بشود.

مسئله‌اي که مي‌خواهيم در اين مقاله حل کنيم، بدين صورت است که فرض کنيد يک جدول سودوکوي خالي داريد و از شما مي‌خواهند مثلاً پنجاه راه حل معرفي کنيد. يعني به پنجاه جدول که خاصيت سودوکو داشته باشد. توجه کنيد که در مسئله ما همه خانه‌ها خالي هستند.

مطالب گفته شده را در برنامه در قالب تابع Produce نوشتم. تابعي كه آرايه مجموعه آغازين (مجموعه پنجاه‌تايي) و مجموعه جواب بعدي (مجموعه ده هزارتايي) و دو عدد تصادفي نقطه شكست و آدرس ذخيره كردن جواب‌ها در مجموعه بعدي را دريافت مي‌كند دو عمل تركيب و جهش را انجام مي‌دهد و در نهايت آرايه‌اي ده‌هزارتايي به عنوان جواب برمي‌گرداند. (كد 5)

2-5 - ارزشيابي مجموعه جواب

اكنون داراي يك آرايه با ده هزار عنصر به عنوان جواب هستيم كه مطمئناً بعضي از اين جواب‌ها نسبت به بقيه بهتر هستند و همان‌طور كه مي‌دانيم، براي ساختن نسل بعد، بايد از جواب‌هايي استفاده كنيم كه از نظر ارزش، داراي رتبه بهتري باشند. بدين‌ترتيب بايد در ادامه جواب‌هاي خود را ارزشيابي كنيم. اين عمل دقيقاً همان تابعRANK است، اما اين‌بار مجموعه ده هزارتايي را ارزشيابي مي‌نمايد و خروجي را در يك آرايه يك بعدي ده‌هزارتايي مي‌ريزد.

2-6- ساختن نسل بعد

کد 6

در اينجا بايد از ميان ده هزار جواب به دست آمده، جواب‌هاي برتر را به عنوان والدهاي نسل بعدي انتخاب كنيم و بقيه را دور بريزيم، اما قبل از انجام اين عمل، ذكر يك مطلب لازم است و آن اين‌كه همان‌طور كه در مقاله قبلي توضيح داده شده يكي از تكنيك‌هاي جالب در الگوريتم‌هاي ژنتيك، نخبه‌گرايي است.

در اين برنامه براي انجام اين كار بدين‌صورت عمل كرديم كه اگر عناصر آرايه ارزش مجموعه والد همه داراي يك مقدار بودند، عمل نخبه‌گرايي را انجام نمي‌دهيم، در غيراين‌صورت، از ميان والد نسل قبلي ده والدي را انتخاب مي‌كنيم كه داراي مقدار تابع ارزش بيشتري بودند و در مجموعه والد نسل بعد قرار مي‌دهيم. (كد 6)

کد 7

با توجه به اين‌كه مجموعه والدهايمان برابر پنجاه عضو است، اگر عمل نخبه‌گرايي انجام شود، بايد چهل عضو باقيمانده را از ميان مجموعه جواب (مجموعه ده‌هزارتايي) انتخاب كنيم، اما اگر نخبه‌گرايي انجام نشود، هر پنجاه عضو از ميان مجموعه جواب انتخاب مي‌شوند. معيار انتخاب نيز كه البته واضح است: عضوهايي انتخاب مي‌شوند كه بيشترين امتياز را از تابع ارزش دريافت كرده باشند. (كد 7)

2-7- ادامه

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

3 - حواشي برنامه

3-1- مدت زمان اجرا

بديهي است در هر اجرا، جواب‌هاي مختلفي به دست مي‌آيد و البته مدت زمان متفاوتي طول مي‌كشد، اما اجراي برنامه با مفسر زبان VB2005 روي يك كامپيوتر +Athlon 64 3000 با 512MB رم حدود ده دقيقه طول كشيد. لذا توقع اجرا در يك چشم به هم زدن را نداشته باشيد. چون همان‌طور كه مي‌دانيد، فضاي حالت مسئله بسيار بزرگ است. به عنوان تفريح مي‌توانيد در حين اجراي برنامه خود نگاهي به راندمان CPU و حجم حافظه مصرفي داشته باشيد.

3-2- كنكاش در كد

يكي از كارهاي جالب مي‌تواند تغيير تعداد مجموعه والد يا تعداد عناصر هر نسل يا افزايش يا كاهش احتمال جهش و مشاهده اثر آن‌ها در مدت زمان اجراي برنامه باشد. علا‌وه بر اين‌ها، تغيير روش تركيب يا جهش نيز مي‌تواند در نوع خود جالب توجه باشد كه البته اين دو مورد آخر، نيازمند مقداري برنامه‌نويسي است. از موارد جالب ديگر، بررسي سيستم در حالتي است كه خود عدد صفر جزء موارد احتمالي قرار گرفتن در خانه‌ها نباشد و مسئله دقيقاً مسئله سودوكو باشد.

3-3- از نوشتن كد تا توضيح كد

نوشتن برنامه در جاي خود مي‌تواند بسيار سخت باشد، ولي نوشتن متن براي توضيح برنامه عملي به مراتب سخت‌تر است. به ويژه كه نويسنده نيز مانند من قلمي ضعيف داشته باشد. در هر حال هر جاي اين مقاله را كه متوجه نشديد، مي‌توانيد به كامنت برنامه مراجعه كنيد و اگر باز نيز مشكلتان حل نشد، حتماً مشكلتان را در قالب ايميل به دفتر مجله بفرستيد تا در اسرع وقت جوابگوي شما باشم.

سورس برنامه

**pasmod** · ۱۰-۲۳-۱۳۸۸, ۰۸:۱۹ بعد از ظهر

سلام. می‌شه لطف کنی‌ منبع رو هم معرفی‌ کنی‌؟

**Astaraki** · ۱۰-۲۳-۱۳۸۸, ۰۸:۲۳ بعد از ظهر

نويسنده : كيوان تيرداد

که در ماهنامه شبکه - بهمن ۱۳۸۵ شماره 73 هم منتشر شده: لينک

**محمد شمس** · ۱۲-۲۴-۱۳۸۸, ۱۰:۱۱ قبل از ظهر

سلام

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

1. اصلا ژنتیک برای حل این مسئله مناسب نیست.

2. انتخاب ساختار ماتریس برای کروموزوم، کاملا اشتباه است. زمان دسترسی به درایه‌های ماتریس، خیلی بیشتر از دسترسی به درایه‌های لیست (یک بعدی) است.

3. تعریف تابع Fitness کاملا غلط است. باید خطاها شمارش بشوند، نه سطر و ستونهای صحیح. این کار به سرعت باعث بوجود آمدن SuperSubject در جمعیت میشود.

4. نخبه گرایی با 10 کروموزوم، صحیح نیست. با توجه به تعداد جمعیت، 10 کروموزوم خیلی زیاد است.

موفق باشید