۲۳۷۸۴پ
per
ارایه ساختار سلسله مراتبی برای الگوریتم بهینهسازی انبوه ذرات به منظور حل مسایل با پارامتر واقعی با الهام از ساختار هولونیک در سیستمهای چندعامله
Hierarchical Particle Swarm Optimization Algorithm for Solving Real Parameter Problems Inspired by Holonic Organization in Multi Agent Systems
/مهدی روشن ضمیر
: علوم مهندسی برق وکامپیوتر
، ۱۳۹۹
، راشدی
۱۱۱ص
چاپی - الکترونیکی
دکتری
مهندسی کامپیوتر، گرایش هوش مصنوعی
۱۳۹۹/۰۶/۲۹
تبریز
در این رساله، سعی شده است با الهام از قابلیتهای عاملها در سیستمهای چندعامله، عملکرد و توانایی الگوریتم بهینهسازی انبوه ذرات را علی‌الخصوص در مواجهه با مسایل پیچیدهتر و دشوارتر افزایش داده و همچنین بر مشکلاتی مانند از دست رفتن سریع تنوع ذرات، همگرایی زودرس، به دام افتادن در بهینههای محلی و عدم تعادل بین اکتشاف و بهرهبرداری غلبه نماییم .با در نظر گرفتن ذرات تشکیل دهنده الگوریتم PSO به عنوان عاملهایی ساده، این الگوریتم به نوعی سیستم چندعامله در نظر گرفته میشود .از سویی دیگر سیستمهای چند عامله قابلیتها و امکانات فراوانی برای مدیریت عاملها مانند سازماندهیهای گوناگون در اختیار دارند .یکی از این سازماندهیها، ساختار هولونیک میباشد .در این پژوهش سعی شده است تا با الهام از این ساختار، ساختاری مشابه برای الگوریتم PSO ارایه گردد .این فرایند در سه گام و با سه دیدگاه انجام شده است .در گام اول با الهام از ویژگیهای بازگشتی، خود متشابه بودن و چند سطحی بودن ساختار هولونیک، ساختاری مشابه با همین ویژگیها برای PSO ارایه شده و مفاهیمی مانند زیر-ذره و ابر-ذره تعریف میگردند .همچنین نحوه بهروزرسانی بردار سرعت و مکان ذرات نیز با توجه به ساختار جدید، به شیوهای تازه انجام میگردد .در گام دوم با الهام از وجود هولونها و گروههای متعدد در سیستمهای چندعامله هولونیک و تشکیل یک ساختار درختی توسط آنها، ذرات نیز در گروههای مختلف دستهبندی شده و با معرفی نماینده برای هر گروه به ایجاد ساختاری سلسلهمراتبی و درختگونه برای تبادل اطلاعات در میان خود اقدام مینمایند .ساختار ایجاد شده همسایگی جدیدی برای ذرات ایجاد کرده و با انتشار مناسب جریان اطلاعات در میان ذرات از همگرایی زودرس جلوگیری کرده و مانعی برای از دست رفتن تنوع ذرات میگردد .همچنین گروهها با تبادل ذرات در میان خود، از به دام افتادن در بهینههای محلی جلوگیری میکنند .از سویی دیگر وجود این ساختار، چندین راهنما را برای هدایت ذرات در دسترس قرار داده تا با استفاده متغیر از اطلاعات این راهنماها در طول اجرای الگوریتم، تعادل مناسبی میان اکتشاف و بهرهبرداری ایجاد گردد .برای انجام این کار دو رابطه جدید برای یادگیری ذرات معرفی شده است .نکته دیگری که در این ساختار در گام دوم وجود دارد این است که تمامی گروهها یکسان و همگن میباشند .در نتیجه تمامی آنها به یک صورت عمل مینمایند .در گام سوم و نهایی از ساختاری مشابه با گام دوم استفاده شده است .اما گروههای تشکیل دهنده این ساختار ناهمگن میباشند .برای ایجاد تعادل بین قدرت اکتشاف و بهرهبرداری الگوریتم، به هر کدام از گروهها وظیفهای تخصیص داده میشود .ذکر این نکته ضروری است که برای بهبود عملکرد الگوریتم PSO روشهای گوناگونی ارایه شده که شامل تنظیم پارامترها، انواع توپولوژیهای همسایگی، روشهای مختلف یادگیری و ترکیب با الگوریتمهای تکاملی دیگر است .مشکل موجود در دیگر روشهای ارایه شده در این است که تنها یکی از این جنبهها را مورد بررسی و استفاده قرار می‌دهند
In this thesis, inspired by agents capability in multi agent systems, it is tried to empower particle swarm optimization algorithm (PSO) and overcome its weaknesses like losing diversity, premature convergence, trapping in local optimums and unsuitable balance between exploration and exploitation. Considering the particles in PSO as simple agents, PSO will be a kind of multi agent system. Multi agent systems have a lot of capabilities and facilities to manage the agents like different organizations. One of these organizations is holonic structure. Inspired by this structure, it is tried to create similar structure for PSO. This goal has been achieved in three phases. In the first phase, inspired by some attributes of holonic organization like self-similarity, recursive and multi-level structure, similar structure is proposed for PSO algorithm. In this phase, some concepts like sub-particle and super-particle are defined. Also, the updating formula for particles velocity is redefined according to the new structure. In the second phase, other facilities of holonic multi agent systems like existence of several groups and holons and tree structure of these groups are used. So, particles in PSO are arranged in different groups and make a hierarchical and tree-like structure by choosing a representative for each group. This structure is used for communication and information sharing between particles and groups. This structure is a new neighborhood topology for particles and prevents from losing diversity and premature convergence by creating a suitable information flow between particles. Meanwhile, this structure helps the particles to jump out of local optimums by swapping particles between groups. This new structure provides several leaders for particles to guide them in the search space. By using the information of these leaders in different manners during the iterations of the algorithm, a suitable balance between exploration and exploitation will be created. For this purpose, two new formulas are defined for particles to learn from leaders. In this structure, all groups are homogeneous. So, all of them act similar to each other. This is the main feature of the proposed structure in the second phase. The structure of the third and final phase is similar to the structure of the second phase but its groups are heterogeneous. For creating a proper balance between exploration and exploitation, different tasks are assigned to these groups. It should be noticed that there are methods to improve the performance of PSO like different parameter settings, neighborhood topologies, learning strategies and combining it with other evolutionary algorithms. One of the weaknesses of other algorithms which are proposed to empower PSO is concentrating and using on only one of these aspects. One of the advantages of the proposed structure in the third phase is its heterogeneous groups. This feature makes it possible to use all the mentioned aspects for empowering PSO, simultaneously. In each group, based on its assigned task, particles use different parameter settings, neighborhood topologies and learning strategies. This structure provides suitable information flow between groups with different tasks. Therefore, it prevents from losing diversity and premature convergence and helps the particles to get rid of these problems. Meanwhile, in order to use the available information properly and solve the Two Steps Forward, One Step Back and oscillation phenomenon problem, a new dimension-by-dimension learning strategy is proposed for particles. Also, a method is proposed to help the particles to get rid of local optimums and solve this problem. In order to evaluate the performance of proposed structures, various types of test functions including unimodal, multimodal, shifted, rotated, shifted rotated, expanded and hybrid composition test functions are used. Proposed algorithm of the second phase are compared with 8 variants of PSO algorithm on 22 benchmark functions. Since the proposed algorithm in the third phase is the final version of the proposed structure, most experiments and analysis have been done on this algorithm. These experiments are conducted using 34 test function on 10 and 30 dimensional cases. The performance of this algorithm are compared with 12 variants of PSO algorithm based on solution accuracy and convergence speed. Also, a rank based analysis and nonparametric Wilcoxon signed rank test at 0.05 significance level are used to evaluate their performance completely. Meanwhile, their algorithmic computational complexity are calculated and compared. All the obtained results indicate the proper performance and superiority of the proposed algorithm compared with other algorithms. The new hierarchical structure has a great impact on the performance of PSO algorithm. On the other hand, a discrete version of proposed algorithm is used to optimize the decision making flowchart in single and multi-agent systems. To evaluate this version of the proposed algorithm, an environment of multi-agent systems named Tile World is used. The results show that the discrete version of proposed algorithm could create a suitable flowchart for agents to help them make proper decisions in different situations
Hierarchical Particle Swarm Optimization Algorithm for Solving Real Parameter Problems Inspired by Holonic Organization in Multi Agent Systems
روشن ضمیر، مهدی
Roshanzamir, Mahdi
بالافر، محمدعلی، استاد راهنما
رضوی، سیدناصر، استاد راهنما
سیاه و سفید
نمایه‌سازی قبلی
