بهینه‌سازی نقشه ساختمان

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

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

-------------------------------------------------------------------------

در استفاده از الگوریتم ژنتیک و فرآیند تکامل باید ژنوم های مورد استفاده ی خود را طوری تعریف کنیم که به پاسخ مسئله کمک کند و ما ژنوم را در مبنای 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 در بعضی موارد شکل اشتباه تولید میکند و فاکتور تداخل در آن بالا خواهد شد.


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

# مراجع
+ علیرضا نوریان، "طراحی نقشه ساختمان با استفاده از محاسبات تکاملی"، پایان‌نامه کارشناسی، دانشگاه علم و صنعت ایران، ۱۳۹۰. [لینک](https://dl.dropboxusercontent.com/u/90405495/undergrad-report.pdf)
+ 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