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

مقدمه

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

کارهای مرتبط

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

در استفاده از الگوریتم ژنتیک و فرآیند تکامل باید ژنوم های مورد استفاده ی خود را طوری تعریف کنیم که به پاسخ مسئله کمک کند و ما ژنوم را در مبنای 2 و با معیار های مسئله ی خود تنظیم میکنیم.
مفهوم جهش در فرآیند حل مسئله ی ما یعنی تغییری اتفاقی در ژن مورد نظر ما که با مبنای دو مدل کردیم بدین صورت که صفر به یک و یک به صفر تبدیل میگردد و در واقع با تحلیل آن ژنوم جدیدی که به تولید پلانی جدید می انجامد تولید میشود یعنی همانطور که گفتیم نسلی جدیدتر (بهتر یا بدتر)ایجاد شده که بخشی از مسئله است.مثلا:00|10|000-->00|11|000 یک نوع تغییر است که به صورت تصادفی در آن قسمت از ژنوم ما روی داده و ما سعی در بررسی و استفاده از این تغییرات داریم.
عملگر دیگر مورد استفاده ی ما ترکیب است که با آن تولید فرزند از روی نسل های گذشته میکنیم و انتقال ویژگی ها از نسل قبل به نسل بعد را از آن انتظار داریم.
در این عملگر یک عدد به طور تصادفی انتخاب میشود و مانند نظریه تکامل در آن قسمت ژنوم دو والد از آن قسمت با هم عوض میشوند.یعنی جای بخش اول از والد اول با جای بخش دوم والد دوم عوض میشود و منجر به تولید دو فرزند میشود که در مسئله ی ما دو پلان مجزای ساختمان تحلیل میشود.
ما سعی داریم که نسل های تولید شده ی ما رو به بهبود و بهتر شدن از جنبه ی فاکتور هایی که تعریف میکنیم بروند.
برای تکامل یافتن نسل ها باید فرزندان بهتری تولید کنیم که این نیاز به انتخاب والد بهتر را مشخص میکند.انتخاب والد به شایستگی های والد ها ربط دارد و آن را هم با فاکتور هایی که تعریف میکنیم بررسی میکنیم.برای انتخاب والد الگوریتم های زیادی وجود دارند.ما از الگوریتم wheel roulette استفاده میکنیم.این الگوریتم به نسبت ساده تر است و بدین صورت است که احتمال انتخاب شدن هر فرد برابر احتمالی است که به آن نسبت داده شده است.
عملگر بعدی ما جایگزینی است.بدین صورت که برای حرکت به سمت جامعه ی مطلوب تر والد ها و فرزندان را با فاکتورهای نام برده مقایسه میکنیم و نسل بعدی را با گزینش میان والد ها و فرزندان انتخاب میکنیم.والد ناشایسته تر را با فرزند شایسته تر جایگزین میکنیم و نسل بعدی را به صورت مطلوب تر ایجا میکنیم.
بعد از تعریف این عملگر ها از الگوریتم های مختلفی بهره میگیریم تا به جواب مطلوبتری برسیم.
آنچه باید انجام دهیم:
کاربر علاقه دارد که با کلیک کردن روی یک دکمه نتیجه ی نقشه ی ساختمان را ببیند.نرم افزار هیچ شناخت خاصی از مساحت و ابعاد اتاق ها ندارد واین را کاربر باید وارد کند.فضای دسترسی بسیار مهم است و نرم افزار برای این کار باید یک هال بزرگ که با کمترین راهرو به همه ی اتاق ها بشود دسترسی داشت را فراهم کند.البته کاربر اختیار دارد بعضی دسترسی ها را خودش تعیین کند.
وظیفه ی دیگر نرم افزار ما در نظر گرفتن معیار های مهم و مطلوب ساختمان مناسب است.مسائلی مثل نورگیری و دسترسی های ممنوع و معیارهایی از این قبیل.
برای حل این مسئله با فرایند تکامل باید هرکدام از اجزای مسئله را با ژنومی متشکل از اعداد حقیقی مدل کنیم و اینگونه در فضای مسئله ی فرایند تکامل وارد کنیم.مثلا طول و عرض و فاصله از مبدا را در ژنوم بیاوریم و روی این اعداد مانور و پردازش ها را انجام دهیم.در واقع ما در این مسئله به اتاق ها و فضاها با اعداد توصیف کننده ی آنها نگاه میکنیم.
عملگرهای فضای این مسئله ی ما:
ادغام اتاق ها:هر فرزند(نقشه) باید اجزایش را از نقشه ی پدر ارث ببرد.مثلا ممکن است دستشویی را از یک والد و اتاق خواب را از والد دیگر به ارث ببرد.
جهش تعویض مکان دو اتاق:این عملگر به معنی مجموعه اعداد توصیف کننده ی اتاق توجه میکند.این عملگر مرکز استقرار دو اتاق را که تصادفی انتخاب شده اند را با هم عوض میکند.
تابع ارزیابی:همانطور که گفتیم تابع ارزیابی جز مهم و لاینفک تکامل است و در این پروژه تابع ارزیابی ما بر اساس عدد های ژنوم باید با روابطی به میزان نزدیکی نقشه به محل قابل سکونت مناسب پی ببرد.معیار هایی مثل فضای دسترسی و مساحت های مناسب اتاق ها و نورگیری و مسائلی ازین دست در تابع ارزیابی ما دخیل هستند.
در فضای دسترسی این مسئله ما سعی داریم با ایجاد مستطیل هایی (با اعداد ژنوم مسئله) فضای خالی مسئله را پر میکنیم و سعی داریم همپوشانی مستطیل هارا کنترل کنیم همپوشانی به این صورت نباید باشد که اتاقی روی اتاقی دیگر بیفتد اما اگر دو مستطیل به طور عمود و افق روی هم بیفتند که هر دو مربوط به فضای هال باشند میتوان هال غیر مستطیل تولید کرد.بزرگترین مستطیل را هال در نظر میگیریم.
در نمایش به کاربر پس از فشردن کلید نقشه به صورت واضح و تفکیک شده نمایش داده میشود و نمره ها و معیار ها نیز در کنار آن نمایش داده میشود تا امکان بررسی و مقایسه هم وجود داشته باشد.نمره هایی از قبیل نورگیری و دسترسی و پرتی و قابلیت اجرا و...
برای پیاده سازی این الگوریتم در حل مسئله ی بهینه سازی نقشه ی ساختمان و آنچه توضیح داده شد با زبان و ظاهر گرافیکی سی شارپ سعی در پیاده سازی آن شده است.

https://github.com/ali-atghaei/AI-project

آزمایش‌ها

برای حل این مسئله دو الگوریتم متفاوت را آزمایش نمودیم:الگوریتم های ژنتیک و الگوریتم چند هدفه.در روش چند هدفه فاکتور تداخل مستطیل های اتاق ها و اشکال بی فایده بسیار زیاد بوده و خیلی دیر و حتی هیچوقت به جواب نمیرسید اما الگوریتم ژنتیک در زمانی تقریبا اندک به جواب میرسد.
در الگوریتم ژنتیک بخش فرایند تولید نسل و تکامل در سرعت و دقت رسیدن به جواب تاثیر بسزایی دارد که پیاده سازی آن کمی دشوارتر و دقیق تر است که ما از کتابخانه ی مخصوص این بخش استفاده کردیم.
در همین الگوریتم های تکامل از الگوریتم hill climbing استفاده شده که در بخش هایی جواب بدی به دست میدهد و پلان بهینه تر از نسل قبل را لزوما تولید نمیکند. خوبی الگوریتم ژنتیک نسبت به تپه نوردی این است که جامع نگری بیشتری دارد و قطعیت جواب بهینه اش بیشتر است.اما الگوریتم تپه نوردی علارقم سرعت بیشتر در مرحله ای به بعد به کل به انحراف رفته و در جوابی غیر مطلوب ماکزیمم نسبی گیر میکند.
در اجرای روش ترکیبی به نتایج قابل قبولی میرسیم که فاکتور جریمه ی آنها بالاتر است و معمولا جریمه ی تداخلش خیلی پایین است اما جریمه های دیگرش بالاتر از روش ژنتیک میشود.در کل الگوریتم ژنتیک نتایج بهتری به دست میدهد.
پیاده سازی پروژه: این نرم افزار از دو بخش اصلی تشکیل میشود یکی بخش اصلی محاسبات و چگونگی ایجاد نقشه ها با توابع و مسائلی که در بالا شرح دادیم و که در نهایت منجر به تولید ژنوم نهایی مسئله میشود.بخش دیگر واسط گرافیکی پروژه بوده که این ژنوم تولید شده را به شکل مفهوم تری به کاربر سیستم نمایش دهد.در این قسمت به توضیح توابع و ماژول های استفاده شده در این دو بخش میپردازیم.
در بخش تحلیل و محاسبات ما از الگوریتم ژنتیک استفاده نمودیم که همانطور که گفته شد بخش خیلی مهم این الگوریتم طراحی و اجرای درست تابع های ارزیابی است.در بخش ارزیابی فاکتورهای نور و دسترسی و عدم تداخل و ابعاد اتاق ها مد نظر هستند که برای این ارزیابی ها از توابعی استفاده شد که در ادامه به بحث در مورد چگونگی کار و کاربرد آنها میپردازیم.
برای پیاده سازی فرایند تکامل از کتابخانه ی paradisٍEo کمک گرفته شده که اجرای مرحله به مرحله ی محاسبات تکاملی را ساده تر میکند بدین صورت که در ابتدای فایل برنامه فایلی که تابع های ارزیابی را نوشته بودیم صدا میزنیم و حال با داشتن تابع ارزیابی و تعریف ما از ژنوم مسئله به اجرای فرایند تکامل پرداخته و حاصل مسئله را تحویل کاربر میدهد.
در تعریف مسئله بدین صورت عمل نمودیم که ژنوم مسئله ی ما در هر مسئله ممکن است متفاوت باشد.یعنی اول با پرسیدن تعداد اتاق های پلان از کاربر به تعیین طول رشته ی ژنوم مسئله میپردازیم.
در تابع تعریف اتاق ها بدین صورت عمل شده که هر اتاق با مختصات دو راس متقابل روی قطر مستطیل تعریف میشود و با این اعداد به سادگی به طول و عرض و مساحت هر اتاق دسترسی داریم و به راحتی در محاسباتمان وارد میکنیم.
در تابعی که برای ارزیابی نور در نطر گرفتیم (light):با توجه به اینکه قرار است ساختمان از جنوب و مشرق نور بگیرد پس هرچه اضلاع اتاق ها با این دو ضلع از ابعاد زمینمان مشترک باشند نور بیشتری به ساختمان خواهد رسید.پس از طریق محاسبات ساده و یک حلقه ی ساده توانستیم معیار نور اتاق ها را ارزیابی کنیم و تابع جریمه ی آن را ایجاد کنیم.
در تعریف تابع دسترسی هم با تشخیص نقطه ی شروع و نقطه ی مرکزی به امتحان اینکه آیا میشود به مرکز همه ی اتاق ها یک پیکان کشید یا خیر عمل نمودیم.
که برای پیاده سازی آن از حلقه ی for و لیست استفاده شده که به وضوح مشخص است.
تابع ابعاد ما در تابع ارزیابی هم بخش مهمی از آن میباشد که بنا به آنچه از کاربر گرفته شده با دیدن و مقایسه کردن مساحت تولید شده و مساحت پیشنهادی کاربر چقدر تفاوت وجود دارد و آن را در تابع جریمه معیار قرار میدهد.
تابع عدم تداخل هم پیاده سازی ساده ای دارد اما نقش بسیار مهمی دارد و در تابع جریمه ی مجموع به آن وزن بیشتری داده ایم.عملکرد آن هم بنا به تعریفمان از چهار مختصات اصلی ایجاد کننده ی اتاق ها طول و عرض مستطیل های اتاق ها به سادگی میتوان فهمید که چقدر تداخل و همپوشانی رخ داده است.
برای واسط گرافیکی به منظور کاربری راحت تر نرم افزار با کاربر از واسط کاربری QT استفاده نمودیم.نحوه ی کار آن هم اینگونه است که در ابتدا کاربر تعداد اتاق ها و طول و عرض زمین را وارد میکند و نرم افزار در نهایت بهینه ترین ژنوم نقشه را با گزارش جزئیات و میزان پرتی و جریمه های نور و دسترسی و ابعاد و همپوشانی به کاربر عرضه میکند.
تابع viewer نوشته شده در برنامه ژنوم تولید شده در بخش تحلیل را بررسی کرده و سعی در ترسیم آن میکند.
در این پیاده سازی هنوز اشکال اندکی در تداخل در بعضی مسائل بدست میداد که با تعویض تابع ارزیابی بخش تداخل این مسئله رفع شد.باید توجه داشت که دیوار بین اتاق ها را در به صورت ضخامت یکسان در نظر گرفت.
برای پیاده سازی این پروژه تحت وب با زبان سمت سرور php زمان تحلیل مسئله بالا بوده و در تحلیل نقشه های بالای 7 اتاق جواب غیر قابل قبول میدهد و در ترسیم این ژنوم با html در بعضی موارد شکل اشتباه تولید میکند و فاکتور تداخل در آن بالا خواهد شد.

کارهای آینده:

این الگوریتم استفاده شده و تست شده ولی فاکتور همپوشانی اتاق ها و یا مستطیل ها که یکی از نکات مهم مسئله ی ماست در فرایند اجرای این الگوریتم خیلی بالا و تقریبا غیر قابل اجتناب است.ولی الگوریتم ژنتیکی که نوشته شده بسیار کاراتر بوده است و به جواب درست میرساند.
توابع ارزیابی استفاده شده در این پروژه محدود بوده اند و معیارهای کامل یک معمار را طبیعتا در نظر نمی گیرد و به چند تابع ضروری اکتفا میکند.فاکتور صدا و پستی بلندی های زمین هم میشود رعایت شود که با محدودیت ژنوم و آرایه ی مورد استفاده ی ما در این مسئله کمی سخت میشد.برای فاکتور سه بعدی(یعنی بلندی های زمین و غیره) می توانستیم از آرایه ی دوبعدی برای ژنوم استفاده کنیم و کتابخانه ی pyevolve در زبان پایتون قسمت فرایند ژنتیک ژنوم دوبعدی میتوانست آن را اجرا کند.
مسئله ی دیگر در فاصله ی این برنامه با کاربرد وسیع آن در کار مسئله ی مستطیل در نظر گرفتن همه ی اتاق ها و زمین بود که در زمین های به شکل ها ی دیگر جواب نمیداد و به نظر میرسد که برای این اشکال هم با در نظر گرفتن ژنوم دو بعدی و این بار با روش های چندهدفه ی ذکر شده پیاده سازی تا حدودی درست را انجام داد.
در مرحله ی پیاده سازی در پایتون از کتابخانه ی pyevolve استفاده کردیم.کتابخانه ی جدیدتر و با امکانات بیشتر deap هم میتواند برای پیاده سازی جالب تر باشد و انتظارات بیشتری را براورده کند.
در فرایند الگوریتم تکامل ما اتاق ها را به صورت مستطیل های مستقل از هم انتخاب کرده بودیم فضای خالی بین فضاها را به صورت اجتناب ناپذیری ایجاد میکرد.می شود به جای این مستطیل ها دیوارها و خطوط حاصل از آنها را در نظر گرفت که البته این حالت هم مشکلات خاص خودش را ایجاد میکند.
روش پیشنهادی دیگر بیان اتاق ها با یک نقطه است.میدانیم هر دیوار دقیقا بین دو نقطه قرار دارد برای تقسیم ساختمان به چند مستطیل (اتاق) با این نقاط ابتدا دیوار بین دو نقطه ی اول را رسم میکنیم تا نقشه به دو بخش تقسیم شود و بعد این کار را برای همه ی بخش ها انجام دهیم تا هر نقطه در یک بخش قرار بگیرد.
که در این روش فاکتور فضای بیهوده کمتر میشود و فضاهای خالی با اتاق ها پر خواهند شد.
روش دیگری که به ذهن میرسد استفاده از نقاط وسط محدوده های نصف شده ی زمین اولیه است.یعنی بدین صورت که ابتدا زمین را 1/2 میکنیم و هر نیمه را نصف میکنیم و این عمل را تا میزانی ادامه میدهیم(مثلا 8 بار) و سپس نقاط وسط هر محدوده را به همراه طول و عرض زمین در جایی ذخیره میکنیم.و از مختصات های نامبرده شده در تابع های ارزیابی و قوانین حاکم بر مسئله استفاده کنیم و ژنوم مسئله را نیز با مشخص کردن طول و عرض نقطه ی وسط
به نصف اندازه ی گذشته کاهش دهیم.
در صورت پیاده سازی این پروژه تحت محیط وب هم میتوان مخاطبان بیشتری کسب کرد و سرعت پیشرفت کار را شدیدا افزایش داد.مشکل طراحی تحت وب پیاده سازی الگوریتم ژنتیک است و با توجه به اینکه در وب سرعت پردازش سرور و برنامه بسیار حائظ اهمیت است کار با این فرایند و اجرای این الگوریتم ها به دلیل زمانبر بودن بیشتر از انتظار کمی دشوار به نظر میرسد.
در بحث کاربری این پروژه نیز باید گفت که با پیشرفت دادن این پروژه میتوان کاربران زیادی را متوجه این کار کرد و استفاده ی فراوانی خواهد داشت.علی الخصوص اگر معیار های معمارانه را به مرور زمان به شکل صحیح دخیل کنیم شاهد استقبال بسیار بزرگ کاربران مربوط خواهیم بود.

مراجع

• علیرضا نوریان، "طراحی نقشه ساختمان با استفاده از محاسبات تکاملی"، پایان‌نامه کارشناسی، دانشگاه علم و صنعت ایران، ۱۳۹۰. لینک

• S. Cahon, N. Melab, and E. G. Talbi, “ParadisEO: A Framework for the Reusable Design of
  Parallel and Distributed Metaheuristics,” Journal of Heuristics, vol. 10, pp. 357-380, May 2004.

• An algorithm for building rectangular floor-plans
  Authors: Sany M. Leinwand University of Illinois, Chicago, Dept. EECS
  Yen-Tai Lai University of Illinois, Chicago, Dept. EECS

• EVACNET+: A computer program to determine optimal building evacuation plans
  Thomas M. Kisko, Richard L. Francis

• Computers & Operations Research, Volume 22, Issue 1, January 1995 , Pages 5-13
  Colin R. Reeves