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

۱. مقدمه

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

۲. کارهای مرتبط

برای این پروژه روش های استراتژی تکاملی و الگوریتم ژنتیک و روش چند هدفه استفاده میشود.که در اینجا به توضیح روش الگوریتم ژنتیک میپردازیم

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

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

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

۳. آزمایش‌ها

۴. کارهای آینده

۵. مراجع

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

• 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