در این پروژه شما با استفاده از خانواده الگوریتم‌های ژنتیک سعی می‌کنید، نقشه‌ای بهینه برای ساختمان طراحی کنید. در واقع محصول شما باید از مساحت زمین مشخص‌شده به عنوان ورودی، بهترین استفاده را برای قرار دادن اتاق‌ها بکند. تعریف دقیق مساله بر عهده خود شماست و می‌توانید دیگر معیارهای یک نقشه خوب، مثل میزان نورگیری فضاها را هم مدل‌سازی کنید.
# مقدمه
بشر همواره به دنبال کسب رفاه بیشتر است.این تلاش در تمام جنبه های زندگیش نمود پیدا کرده است.افق نهایی این پروژه نیز همچون گذشته، در این راستاست.هدف نهایی پروژه، هوشمند کردن طراحی نقشه ساختمانی است.به طوری که ماشین، طرح بهینه یک نقشه را بدون دخالت انسان انجام دهد.
ما در اینجا برای شروع، مساله را به اندازه کافی کوچک و محدود خواهیم کرد.برای این کار فرض میکنیم زمین و اتاق ها به شکل مستطیل است. و ورودی برنامه به این شکل خواهد بود که کاربر ابعاد زمین ، تعداد اتاق هایی که میخواهد و همچنین مساحت کوچکترین و بزرگترین اتاق را تعیین میکند.
برای این کار الگوریتم های متفاوتی وجود دارد،ما در این پروژه قصد داریم از الگوریتم ژنتیک استفاده کنیم.هدف، تولید نقشه مطلوب و مشتری پسند است.یعنی اتاق ها باید به گونه ای باشد که اولا راه دسترسی به اتاق ها صحیح باشد و ثانیا نور مناسب به هریک از بخش های خانه برسد.
از کاربردهای این پروژه، اولا می توان به تهیه نقشه های معماری به طور هوشمند و بدون دخالت انسان اشاره کرد.ثانیا میتوان از طراحی مدارات مجتمع بزرگ مقیاس نام برد.
# کارهای مرتبط
موضوع این پروژه به مساله تخصیص فضا مشهور است.به معماران، در بدست آوردن نظم های مختلف المان های نقشه ، کمک می کند. برای حل این مساله و خودکار کردن آن، تلاش های بسیاری انجام گرفته است. که حاصل آن بدست آوردن الگوریتم های متفاوت می باشد.یکی از این الگوریتم ها، الهام گرفته از طراحی های مدارات بزرگ مقیاس است. به این صورت که برنامه تعدادی اتاق با مشخصه ها، اولویت ها و ضوابط مختلف می گیرد و آنها را همچون بلوک های یک مدار بزرگ مقیاس در کنار یکدیگر نظم می دهد.[2]یکی دیگر از کارهایی که نسبتا جدید در این زمینه صورت گرفته است، تهیه نقشه معماری از یک آپارتمان یک خوابه است. روش کار به این صورت است که در رابطه با ارتباط اتاق ها با یکدیگر جست و جو انجام میدهد. و نتیجتا فهرستی از حالات ممکن را نمایش می دهد.[2] یکی دیگر از الگوریتم هایی که برای این کار استفاده می شود، الگوریتم ژنتیک است. در الگوریتم ژنتیک تابع ارزیابی و نسل ها وجود دارند. مکانیزم این الگوریتم برگرفته از طبیعت است. به این صورت که بالاخره ما می توانیم از توالی نسل ها، به خروجی مورد نظر برسیم.[1] یکی دیگر از الگوریتم هایی که میتواند مورد استفاده واقع شود، الگوریتم استراتژی تکاملی است.این الگوریتم برای مسائل بهینه سازی در فضای پیوسته کارایی دارد.این الگوریتم دارای بخش های جهش، ترکیب و جایگزینی است. [1]
# آزمایش‌ها
در فاز پیاده سازی، فقط الگوریتم ژنتیک را پیاده سازی نمودیم.برای این کار از ماژول deap زبان پایتون استفاده شده است.
توضیحات کد:
در ابتدا از کاربر ابعاد زمین خام را میگیریم. سپس تعداد اتاق ها و همچنین کمترین و بیشترین مساحت اتاق را توسط کاربر مشخص میکنیم.
سپس در محدوده ی ابعاد زمین، دنباله ی تصادفی از کرومزوم ها را با استفاده از توابع آماده ماژول مورد استفاده، تولید نموده ایم.در مرحله ی بعد، تابع برازندگی که خود شامل چند تابع دیگر است را تعریف کردیم.آنگاه با استفاده از قوانین حاکم در الگوریتم ژنتیک به تولید نسل های مختلف پرداختیم. توجه داشته باشید که فرض بر آن است که تعداد نسل ها، 80 باشد.
آزمایش کد:
برای آزمایش ورودی های مختلف را به برنامه دادیم و خروجی برنامه که به صورت آرایه است را دریافت کردیم.آرایه شامل مختصات دوتا از گوشه های مستطیل(اتاق ها) می باشد. زیرا با داشتن مختصات دو گوشه ی مخالف یک مستطیل، به راحتی می توان آن را ترسیم نمود.در این کد نیز،هر چهار عدد پشت سرهم در آرایه ، نشان دهنده ی طول و عرض دو گوشه ی یک مستطیل میباشد.
مشکلاتی که وجود دارد، اولا کامل نبودن تابع برازندگی است.از این جهت که نور و فضاهای مرده به طور کامل مدیریت نمی شود. اما خروجی ای که داده میشود، برهم افتادگی و همپوشانی مستطیل ها دیده می شود.برای بهبود نتیجه احتمالا تابع برازندگی را باید بهبود بخشید.
لینک پروژه در bitbucket :
https://bitbucket.org/arman_p/blueprint-optimization
# کارهای آینده
تابع برازندگی استفاده شده در این برنامه، تنها ملاک‌های برهم‌پوشانی اتاق‌ها و نور را ملاک قرار میدهد. این برنامه به‌طور کلی، آنچنان که در افق نهایی پروژه آمده‌است، ما را از یک معمار بی‌نیاز نمی‌کند. یک معمار واقعی ملاک های دیگری همچون پستی و بلندی زمین، جهت باد، شکل خانه‌های همسایه و شرایط اقلیمی دیگر را در نظر می‌گیرد.
برای عملی کردن ملاک پستی و بلندی، میتوان یک آرایه دو بعدی متشکل از کروموزوم ها را تعریف کرد. این کار به سادگی با استفاده از ماژول deap که در این پروژه استفاده شده است، قابل پیاده‌سازی است.
مسئله ی دیگر در فاصله ی این برنامه با کاربرد وسیع آن در کار مسئله ی مستطیل در نظر گرفتن همه ی اتاق ها و زمین بود که در زمین های به شکل ها ی دیگر جواب نمیداد و به نظر میرسد که برای این اشکال هم با در نظر گرفتن ژنوم دو بعدی و این بار با روش های چندهدفه ی ذکر شده پیاده سازی تا حدودی درست را انجام داد.
روش پیشنهادی بیان اتاق ها با یک نقطه است.میدانیم هر دیوار دقیقا بین دو نقطه قرار دارد برای تقسیم ساختمان به چند مستطیل (اتاق) با این نقاط ابتدا دیوار بین دو نقطه ی اول را رسم میکنیم تا نقشه به دو بخش تقسیم شود و بعد این کار را برای همه ی بخش ها انجام دهیم تا هر نقطه در یک بخش قرار بگیرد.که در این روش فاکتور فضای بیهوده کمتر میشود و فضاهای خالی با اتاق ها پر خواهند شد [6].
روش دیگری که به ذهن میرسد استفاده از نقاط وسط محدوده های نصف شده ی زمین اولیه است.یعنی بدین صورت که ابتدا زمین را 1/2 میکنیم و هر نیمه را نصف میکنیم و این عمل را تا میزانی ادامه میدهیم(مثلا 8 بار) و سپس نقاط وسط هر محدوده را به همراه طول و عرض زمین در جایی ذخیره میکنیم.و از مختصات های نامبرده شده در تابع های ارزیابی و قوانین حاکم بر مسئله استفاده کنیم و ژنوم مسئله را نیز با مشخص کردن طول و عرض نقطه ی وسطبه نصف اندازه ی گذشته کاهش دهیم [6] .
می توان برای دقیق‌تر کردن این پروژه متناسب با نیاز کاربران، نوعی یادگیری ماشین تعریف کرد. به این صورت که در خروجی، باتوجه به تابع برازندگی و امتیاز‌دهی های آن، یک یا چند خروجی را تولید کنیم. سپس با توجه به اینکه هربار، کاربر(انسان) کدامیک از طرح ها را انتخاب میکند، یک پایگاه دانش قائل شویم. اطلاعات این پایگاه دانش، انتخاب کاربر و ملاکی است که وی برای انتخاب خود در‌نظر گرفته است، میباشد.
# مراجع
+ [1] علیرضا نوریان، "طراحی نقشه ساختمان با استفاده از محاسبات تکاملی"، پایان‌نامه کارشناسی، دانشگاه علم و صنعت ایران، ۱۳۹۰. [لینک](https://dl.dropboxusercontent.com/u/90405495/undergrad-report.pdf)
+ [2] Paul Merrel , Eric Schkufza , Vladlen Koltun ; Compute-Generated Residential Building Layouts ; Stanford University
+ [3] Suphachai Sutanthavibul , Eugene Shragowitz , Member , IEEE and J.B Rosen ; An Analitycal Approach To FloorPlan Design and Optimization
+ [4] S. Cahon, N. Melab, and E. G. Talbi, “ParadisEO: A Framework for the Reusable Design ofParallel and Distributed Metaheuristics,” Journal of Heuristics, vol. 10, pp. 357-380, May 2004.
+ [5]An algorithm for building rectangular floor-plansAuthors: Sany M. Leinwand University of Illinois, Chicago, Dept. EECSYen-Tai Lai University of Illinois, Chicago, Dept. EECS
+ [6]http://www.boute.ir/iust-ai-92/plan-optimization