>> نگاهی به الگوریتم بهینه سازی ازدحام ذرات <<
فابل پاورپوینت
Particle Swarm Optimization
- شروع کننده موضوع nice_Alice
- تاریخ شروع
>> نگاهی به الگوریتم بهینه سازی ازدحام ذرات <<
فابل پاورپوینت
الگوریتم بهینه سازی ازدحام ذرات:
یکی از روش های مطرح در زمینه بهینه سازی، الگوریتم ازدحام ذرات می باشد. این روش در سال 1995 برای اولین بار توسط کندی و ابرهارت ارائه گردید. این الگوریتم از رفتارهای اجتماعی یک دسته از پرندگان و گروهی از ماهی ها در یافتن غذا الهام گرفته شده است(کندی و ابرهارت، 1995). اساس این الگوریتم بر تکرار جستجو در محیط مسئله توسط جمعیت تصادفی می باشد که در هر تکرار ،تابع شایستگی مورد ارزیابی قرار می گیرد و سپس بهترین موقعیت هر پرنده و بهترین موقعیت تمام پرندگان در آن نسل در دو حافظه(بهترین موقعیت محلی ، بهترین موقعیت کلی ) قرار می گیرند.
سپس در نسل بعد جمعیت جدیدی جایگزین جمعیت قبلی می شوند. و در این نسل نیز بهترین موقعیت محلی و بهترین موقعیت کلی با آنچه در نسل قبلی بدست آمد مورد مقایسه قرار می گیرد. در واقع حرکت پرندگان در این الگوریتم به دو عامل حرکت فردی و حرکت جمعی وابسته است. ترکیب این دو حرکت منجر به ایجاد یک مدل کار آمد جهت یافتن بهترین نقطه هدف در مسائل بهینه سازی می شود. اگر پرندگان فقط به حرکت فردی توجه کنند، بزودی گروه یا دسته آنها از هم پاشیده و هر کدام به سمتی خواهند رفت و اگر آنها فقط بدنبال بهترین فرد گروه حرکت کنند ، ممکن است آنها راه را گم کرده و یا در مینیمم های محلی گرفتار شوند و یا دیر به مقصد برسند.
هدف از بهینه سازی، یافتن نقاطی است که در یک تابع هزینه مشخصی ،باعث ایجاد کمترین مقدار شوند و بهینه سازی، فرآیندی است که در آن با انجام تغییرات متوالی در ورودی های اولیه ، منجر به کسب نتایج بهتری در جستجوی نقاط بهینه شود. بعضی از توابع آزمون وجود دارند که دارای اکسترمم های محلی می باشند و این امر می تواند محک مناسبی برای الگوریتم های پیشنهادی جهت حل یک مسئله بهینه سازی واقع شوند. علاوه بر این از دیگر ویژگی های یک الگوریتم بهینه سازی، سرعت و همچنین عدم نیاز به مشتق گیری می باشد. الگوریتم های تکاملی همچون الگوریتم ژنتیک، الگوریتم گروه ذرات و الگوریتم سیستم ایمنی مصنوعی از این ویژگی ها برخوردارند.
همانطور که در بالا گفته شد، روش ازدحام ذرات متاثر از دو مؤلفه شناختی و اجتماعی می باشد. این بدین معنی است که موقعیت یک پرنده در یک مرحله، مؤلفه ای از موقعیت قبلی ،بهترین موقعیت فردی که آن پرنده تا کنون تجربه کرده و بهترین موقعیتی که در کل اجتماع پرندگان تاکنون تجربه شده می باشد.
فرض کنیم تعداد جمعیت پرنده ها n باشد و هر پرنده در ابتدا بطور تصادفی دارای موقعیت xi باشد. در اینصورت الگوریتم ازدحام ذرات بصورت زیر عمل خواهد کرد:
بهترین موقعیت فردی(pbest) و بهترین موقعیت جمعی(gbest) را عدد دهی می کنیم.
برای هر پرنده به صورت تصادفی موقعیتx_i را تولید می کنیم.
برای هر ذره i تابع شایستگی y_i در موقعیت فعلی x_i ارزیابی شود.
اگر y_i بزرگتر از pbesti باشد، آنگاه pbest_i بروز رسانی می شود.
اگر y_i بزرگتر از gbesti باشد، آنگاه〖gbesti 〗_i بروز رسانی می شود.
برای هر ذره سرعتv_i و موقعیتx_i بروز رسانی می شود.
v_i=w*v_i+c_1*r_1*(x_i-〖pbest〗_i)+c_2*r_2*(x_i-gbest_i)
X_i=x_i+v_i
که در رابطه مربوط به سرعت، عبارت (w*v_i) ، اینرسی حرکت می باشد. در واقع w را وزن اینرسی می نامند که معمولا عددی کوچکتر از یک است. c_1=c_2=2 وr_2, r_1 که از اعداد تصادفی بین 0 و 1 می باشند.
عبارتc_1*r_1*(x_i-〖pbest〗_i) را جزء شناختی و عبارتc_2*r_2*(x_i-gbest_i) را جزء اجتماعی الگوریتم ازدحام ذرات می نامند. اگر مقدارc_1=0 شود آنگاه حرکت پرنده کاملا به اراده جمع بستگی دارد و اگر c_2=0 آنگاه پرنده به صورت کاملا خود محور حرکت کرده و توجهی به اراده جمع ندارد.
یکی از روش های مطرح در زمینه بهینه سازی، الگوریتم ازدحام ذرات می باشد. این روش در سال 1995 برای اولین بار توسط کندی و ابرهارت ارائه گردید. این الگوریتم از رفتارهای اجتماعی یک دسته از پرندگان و گروهی از ماهی ها در یافتن غذا الهام گرفته شده است(کندی و ابرهارت، 1995). اساس این الگوریتم بر تکرار جستجو در محیط مسئله توسط جمعیت تصادفی می باشد که در هر تکرار ،تابع شایستگی مورد ارزیابی قرار می گیرد و سپس بهترین موقعیت هر پرنده و بهترین موقعیت تمام پرندگان در آن نسل در دو حافظه(بهترین موقعیت محلی ، بهترین موقعیت کلی ) قرار می گیرند.
سپس در نسل بعد جمعیت جدیدی جایگزین جمعیت قبلی می شوند. و در این نسل نیز بهترین موقعیت محلی و بهترین موقعیت کلی با آنچه در نسل قبلی بدست آمد مورد مقایسه قرار می گیرد. در واقع حرکت پرندگان در این الگوریتم به دو عامل حرکت فردی و حرکت جمعی وابسته است. ترکیب این دو حرکت منجر به ایجاد یک مدل کار آمد جهت یافتن بهترین نقطه هدف در مسائل بهینه سازی می شود. اگر پرندگان فقط به حرکت فردی توجه کنند، بزودی گروه یا دسته آنها از هم پاشیده و هر کدام به سمتی خواهند رفت و اگر آنها فقط بدنبال بهترین فرد گروه حرکت کنند ، ممکن است آنها راه را گم کرده و یا در مینیمم های محلی گرفتار شوند و یا دیر به مقصد برسند.
هدف از بهینه سازی، یافتن نقاطی است که در یک تابع هزینه مشخصی ،باعث ایجاد کمترین مقدار شوند و بهینه سازی، فرآیندی است که در آن با انجام تغییرات متوالی در ورودی های اولیه ، منجر به کسب نتایج بهتری در جستجوی نقاط بهینه شود. بعضی از توابع آزمون وجود دارند که دارای اکسترمم های محلی می باشند و این امر می تواند محک مناسبی برای الگوریتم های پیشنهادی جهت حل یک مسئله بهینه سازی واقع شوند. علاوه بر این از دیگر ویژگی های یک الگوریتم بهینه سازی، سرعت و همچنین عدم نیاز به مشتق گیری می باشد. الگوریتم های تکاملی همچون الگوریتم ژنتیک، الگوریتم گروه ذرات و الگوریتم سیستم ایمنی مصنوعی از این ویژگی ها برخوردارند.
همانطور که در بالا گفته شد، روش ازدحام ذرات متاثر از دو مؤلفه شناختی و اجتماعی می باشد. این بدین معنی است که موقعیت یک پرنده در یک مرحله، مؤلفه ای از موقعیت قبلی ،بهترین موقعیت فردی که آن پرنده تا کنون تجربه کرده و بهترین موقعیتی که در کل اجتماع پرندگان تاکنون تجربه شده می باشد.
فرض کنیم تعداد جمعیت پرنده ها n باشد و هر پرنده در ابتدا بطور تصادفی دارای موقعیت xi باشد. در اینصورت الگوریتم ازدحام ذرات بصورت زیر عمل خواهد کرد:
بهترین موقعیت فردی(pbest) و بهترین موقعیت جمعی(gbest) را عدد دهی می کنیم.
برای هر پرنده به صورت تصادفی موقعیتx_i را تولید می کنیم.
برای هر ذره i تابع شایستگی y_i در موقعیت فعلی x_i ارزیابی شود.
اگر y_i بزرگتر از pbesti باشد، آنگاه pbest_i بروز رسانی می شود.
اگر y_i بزرگتر از gbesti باشد، آنگاه〖gbesti 〗_i بروز رسانی می شود.
برای هر ذره سرعتv_i و موقعیتx_i بروز رسانی می شود.
v_i=w*v_i+c_1*r_1*(x_i-〖pbest〗_i)+c_2*r_2*(x_i-gbest_i)
X_i=x_i+v_i
که در رابطه مربوط به سرعت، عبارت (w*v_i) ، اینرسی حرکت می باشد. در واقع w را وزن اینرسی می نامند که معمولا عددی کوچکتر از یک است. c_1=c_2=2 وr_2, r_1 که از اعداد تصادفی بین 0 و 1 می باشند.
عبارتc_1*r_1*(x_i-〖pbest〗_i) را جزء شناختی و عبارتc_2*r_2*(x_i-gbest_i) را جزء اجتماعی الگوریتم ازدحام ذرات می نامند. اگر مقدارc_1=0 شود آنگاه حرکت پرنده کاملا به اراده جمع بستگی دارد و اگر c_2=0 آنگاه پرنده به صورت کاملا خود محور حرکت کرده و توجهی به اراده جمع ندارد.
بهینه سازی گروه ذرات
بهینه سازی گروه ذرات
بهینه سازی گروه ذرات
فصل یکم : بهینه سازي دستۀ ذرات
فصل دوم : پیاده سازي
فصل سوم : جمع بندي و نتیجه گیري
بهینه سازی گروه ذرات
بهینه سازی گروه ذرات
فصل یکم : بهینه سازي دستۀ ذرات
فصل دوم : پیاده سازي
فصل سوم : جمع بندي و نتیجه گیري