آقای امین نیک انجام دانشجوی دکترای جناب آقای دکتر عادل ترکمان رحمانی روز دوشنبه مورخ 12/4/91 ساعت 9 صبح در اتاق 102 واقع در طبقه اول دانشکده مهندسی کامپیوتر از رساله دکترای خود تحت عنوان بهبود کارایی مدل سازی در الگوریتم های تخمین موضوع دفاع خواهند نمود.

 چکیده پایان نامه:

  الگوریتم‌های تخمین توزیع نوعی از الگوریتم‌های تکاملی هستند که در دهه گذشته به طور گسترده‌ برای حل مجموعه متنوعی از مسائل بهینه‌سازی به کار رفته‌اند. در این الگوریتم‌ها به جای استفاده از عملگرهای ژنتیکی سنتی، در هر نسل یک مدل احتمالی از راه‌حل‌های برگزیده جمعیت ساخته می‌شود. این مدل نشان‌دهنده‌ی وابستگی‌ها و ارتباط اجزای مسأله است و برای یادگیری آن از جمعیت معمولاً از روش‌های یادگیری ماشین استفاده می‌شود. این الگوریتم‌ها دو گلوگاه کارایی دارند: ساخت مدل و ارزیابی راه‌حل‌ها، که دومی در بین همه الگوریتم‌های تکاملی مشترک است. برای حل مسائل پیچیده نمی‌توان از مدل‌های ساده بهره گرفت اما هر چه مدل و به تبع آن روش یادگیری پیچیده‌تر باشد، کارایی الگوریتم کاهش می‌یابد. بنابراین روش‌های متعددی برای بهبود کارایی الگوریتم‌های تخمین توزیع ارائه شده است.

  هدف این رساله بهبود کارایی مدل‌سازی در الگوریتم‌های تخمین توزیع است به ترتیبی که هزینه محاسباتی ساخت مدل کاهش یابد. رویکرد پیشنهادشده برای بهبود کارایی مبتنی بر تعامل‌های زوج‌متغیرها (وابستگی‌های دومتغیره) است. در ابتدا و پیش از شروع الگوریتم تکاملی ماتریس تعامل که دربردارنده وابستگی‌های دومتغیره است، با روش کارآمدی محاسبه می‌شود. از اطلاعات ماتریس به دو شیوه می‌توان استفاده کرد: 1- استخراج مستقیم گروه‌های پیوندی و حل مسأله بهینه‌سازی به کمک این گروه‌ها، 2- ایجاد مدل مناسب بر مبنای این اطلاعات. در این رساله هر دو شیوه مدنظر قرار گرفته‌اند. ابتدا الگوریتم جدیدی برای خوشه‌بندی ماتریس تعامل ارائه شده است که گروه‌های پیوندی را با کارایی و دقت بالایی بدست می‌آورد. سپس الگوریتم تکاملی بر مبنای این گروه‌ها، مسأله بهینه‌سازی را به سادگی حل می‌کند. همچنین روشی برای یادگیری شبکه بیزی، به عنوان یک مدل پرکاربرد در الگوریتم‌های تخمین توزیع، بر اساس ماتریس تعامل ارائه شده است. نتایج به دست آمده نشان می‌دهد به کمک روش پیشنهادی، سرعت یادگیری شبکه بیزی در مسائل آزمایشی افزایش می‌یابد. با بهبود کارایی یادگیری شبکه بیزی، کارایی الگوریتم تخمین توزیع مبتنی بر شبکه بیزی نیز بهتر می‌شود.

  واژه‌های کلیدی: الگوریتم‌های تخمین توزیع، مدل‌سازی، بهبود کارایی، تعامل‌های دوتایی.

 : Abstract

 
Estimation of Distribution Algorithms (EDAs) are a class of evolutionary algorithms which have been used successfully to solve many different problems. In these algorithms, a probabilistic model is built which captures the dependency relationships among problem variables. In this way, the crucial problem of linkage learning is addressed effectively. The model is then sampled to generate new individuals. Various EDAs have been proposed that employ different models to learn linkages. However, building an appropriate model is distinguished as a computationally expensive task and considered as a potential bottleneck. Therefore, many researchers have focused on enhancing the efficiency of model building in EDAs.

  In this dissertation, we propose some new algorithms to improve the efficiency of model building in EDAs. The basic idea is based on pair-wise dependencies. These dependencies are computed efficiently using an appropriate metric and stored in the interaction matrix. This matrix may be used in two different ways: to be clustered to extract linkage groups and to be extended to a proper model. Both of these approaches are addressed in this dissertation. In the first approach, a new clustering algorithm is proposed that turns the interaction matrix into linkage groups efficiently. The model building process is carried out before the evolutionary algorithm to save computational burden. The accurate groups obtained in this way are then used to perform an effective recombination of building blocks (BBs) in the evolutionary algorithm. We applied the proposed approach to solve exemplar hard optimization problems with different types of linkages to show the effectiveness and efficiency of the proposed approach. Theoretical analysis and experiments showed that the building of an accurate model requires O(nlog(n)) number of fitness evaluations. The comparison of the proposed approach with some existing algorithms revealed that the efficiency of the model building process is enhanced significantly.

  In the second approach, an efficient algorithm is proposed to build a Bayesian network based on the pair-wise interaction between problem variables. Learning an accurate skeleton only at the beginning of the algorithm reduces the computational complexity of model building significantly. We employ the proposed approach to find the optimum solution in different optimization problems with different types of linkages. The theoretical and experimental results show that the proposed approach enhances the efficiency of model building and leads to considerable speedups in the number of fitness evaluations and overall execution time of the algorithm.

  Keywords: Estimation of Distribution Algorithms, Model Building, Efficiency Enhancement, Pair-wise Interactions.

  ارائه­دهنده:

  امین نیک انجام

  nikanjam@iust.ac.ir

  استاد راهنما:

  دکتر عادل ترکمان رحمانی

  هیات داوران:

  1- دکتر سعید باقری شورکی2 -دکتر حمید بیگی3- دکتر محمدرضا جاهد مطلق

  4- دکتر محمدرضا کنگاوری 5-دکتر بهروز مینایی

  زمان : دوشنبه 12 تیرماه 1391

  ساعت 9 صبح

  مکان: دانشکده مهندسی کامپیوتر- طبقه اول- کلاس 102

  از اساتید بزرگوار، دانشجویان گرامی و دیگر متخصصان و علاقه مندان به موضوع دفاعیه دعوت
می شود با حضور خود موجبات غنای علمی و ارتقای کیفی را فراهم سازند.

  دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی