ارائه یک الگوریتم برنامه‌نویسی شبکه‌ای برای تصمیم‌گیری در محیط‌های قطعی و غیرقطعی

STUDENT

DEGREE

YEAR

Genetic Network Programming (GNP) is one of the evolutionary methods that have shown outstanding capabilities in optimizing decision making process in agents’ behavior control problem. In GNP, each individual’s structure is a flowchart represented by a directed graph. This flowchart specifies the order in which certain conditions must be checked and suggests recommended actions based on the satisfied conditions. This way the solution to different kinds of complex problems can be modeled. In this work, a novel evolution process for graph-based individuals is presented such that not only the performance and convergence to optimal solution is improved, but also it can cope with stochastic environments. When the environment is stochastic, the agents face a major challenge since the fitness evaluation of the agents are no longer deterministic. In other words, multiple fitness evaluation of the same individual yields different results. This is due to the fact that taking a specific action in an observed state may lead to different next states. Under such conditions, to estimate an individual’s fitness accurately, one is forced to evaluate the individual multiple times and consider the expectation of the observed fitness values as the individual’s fitness. Considering that the evolution process is population-based, multiple fitness evaluation per individual slows down the learning speed drastically. Reducing the number of evaluations per individual is not an option here since less evaluation means less accurate fitness estimation. Inaccurate fitness values mislead the evolution operators such as cross-over and mutation. This in turn results in low quality solutions found by the evolutionary method. In the original GNP method, the cross-over and mutation operators break the structure of the individuals and combine them in different ways. This approach may yield better individuals but it may also destroy good individuals found so far increasing the time needed to reach the desired solution. The proposed approach in this thesis, deals with both issues very well in two steps. In the first step, to determine the destination for each connection, the rewards obtained during the evolution process is distributed on the connections based on the evaluated fitness values. To perform this, the experiences gained by the individuals are accumulated in a table based on which the individuals of the next generation are created. This technique reduces the probability of breaking useful structures in the individuals. The second step, further mitigates the useful structure destruction and improves the fitness estimation of the individuals. Instead of evaluating each individual multiple times, we exploit the set of experiences gained by similar individuals to estimate their fitness and the value of extracted common sub-structures. This advantage of this technique is two folds. First, the fitness values are estimated accurate enough while avoiding multiple evaluations per individual. Second, the extracted useful sub-structures can be used to form better individuals for the next generation. Our proposed method can handle useful sub-structures during the evolution process very well. These sub-structures are transferred from one generation to another efficiently. We have used our method to solve the problem of agents’ behavior control on stochastic version of Tile world and Pursuit domain environments. The observed results suggest that the proposed method can generate effective flowcharts to perform robust decision making. The proposed method is able to find better solutions faster than the original GNP and its variants even in the presence of stochasticity. The superiority of our method is more apparent in the Pursuit domain due to its highly dynamic nature Keywords: Genetic Network Programming, Agents’ Control Problem, Maximal Common Subgraph, Ant Colony Optimization

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