که n_t بیشینه تعداد تکرار،  مقدار اولیه وزن اینرسی،  مقدار نهایی وزن اینرسی و  مقدار اینرسی در زمان t است. نکته آنکه  .
۳٫ کاهش غیر خطی؛ که مقادیر زیاد اینرسی به صورت غیر خطی، به مقادیر کم کاهش می‌یابد. در روش‌های کاهش غیر خطی، زمان اکتشاف کم‌تر از روش‌های کاهش خطی است و در مقابل زمان استخراج بیشتر است. روش‌های کاهش غیر خطی، بیشتر برای فضاهای جستجوی نرم مناسب هستند.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

۲-۵-۲- چالش‌ها و مسائل پیش روی الگوریتم بهینه‌سازی ازدحام ذرات

بهینه‌سازی ازدحام ذرات یک الگوریتم بهینه‌سازی الهام گرفته از طبیعت است که ثابت شده در مسائل بهینه‌سازی بسیاری به خوبی کار می‌کند. از اواسط دهه نود میلادی که PSO ارائه شد کارهای بسیاری برای ارتقاء آن صورت گرفته و در سال‌های اخیر PSO در محدوده وسیعی از کاربردهای گوناگون بکار گرفته شده است. مسائل بسیاری از جمله گیر افتادن در بهینه محلی، واگرایی، سرعت پایین همگرایی، توانایی حل مسائل بهینه‌سازی با ابعاد بالا از چالش‌های الگوریتم پایه‌ی PSO محسوب می‌شدند.
آی دی فالکو^[۳۰] و همکاران [۴۲, ۴۳] ارتباطاتی میان اندازه مسأله و کارایی PSO از طریق نتایج تجربی بدست آوردندد. نتایج بدست آمده نشان می‌داد که مسائل دسته‌بندی دو کلاسه به خوبی توسط PSO مورد ملاحظه قرار می‌گیرد اما نتایج روشنی برای مسائل سه کلاسه یا بیشتر مشاهده نمی‌شود. ضمن اینکه دقت دسته‌بندی با افزایش تعداد کلاس‌ها و همچنین افزایش سایز مسئله کاهش می‌یابد. نوآریا^[۳۱] و بوکادوم^[۳۲] [۴۴] مکانیسم‌های چاره سازی برای مجموعه داده‌های با ابعاد بالا ارائه دادند.
در بازبینی که روی کارهای اخیر در دسته‌بندی به کمک الگوریتم PSO صورت گرفته [۴۵] دو مشکل به صورت متناوب در به‌کارگیری این الگوریتم به چشم می‌خورد: یکی ابعاد بالا^[۳۳] برای داده‌های ورودی که ممکن است اندازه بزرگ پایگاه داده نیز با آن ترکیب شود. مشکل دیگر این که چگونه با داده‌هایی که میان ویژگی‌های آن‌ها همبستگی^[۳۴] وجود دارد برخورد کنیم. توانایی برخورد با مجموعه داده با ابعاد بالا و یا دارای همبستگی میان مشخصه‌ ها از چالش‌های تمام الگوریتم‌های تکاملی می‌باشد.

۲-۵-۲-۱- مشکل ابعاد بالا

دسته‌بندی برای داده‌هایی که دارای خصیصه‌های ابعاد بالا هستند بسیار رخ می‌دهد. فَن^[۳۵] و همکاران [۴۶] تأثیر بالا بودن ابعاد را در عملیات دسته‌بندی مطالعه کردند. آن‌ها اشاره می‌کنند که سختی دسته‌بندی برای ابعاد بالا به طور ذاتی برخاسته از وجود ویژگی‌های نویز دار است که در کاهش خطای دسته‌بندی همکاری نمی‌کنند. دسته‌بندی که از تمام خصیصه‌ها استفاده می‌کند می‌تواند به اندازه حدس زدن تصادفی ضعیف عمل کند. این امر به علت انباشتگی نویز که عموماً به خاطر تخمین اشتباه مرکز جمعیت در فضای ویژگی‌های با ابعاد بالا است رخ می‌دهد. بنابراین، انتخاب زیرمجموعه‌ای از ویژگی‌ها که اهمیت بیشتری دارند برای دسته‌بندی با ابعاد بالا بسیار حائز اهمیت است.
De Falco و سایرین [۴۳] اثربخشی PSO را در دسته‌بندی داده‌ها از مجموعه داده‌های مختلف ارزیابی کردند، که در میان آن‌ها چند مجموعه داده با ابعاد بالا نیز وجود داشت. آن‌ها مجموع تعداد نمونه‌های داده را (D)، تعداد کلاس‌هایی که داده‌ها در آن قرار می‌گیرند © و مجموعه پارامترهایی که هر یک از نمونه‌ها دارند را (N) نامیدند و ادعا کردند رابطه‌ای میان کارایی PSO و حاصل ضرب از یک سو و C از سمت دیگر وجود دارد. نتایج آن‌ها نشان داد دقت دسته‌بندی PSO با افزایش مقدار C و همین‌طور افزایش P تمایل به کاهش دارد.
مجموعه داده‌های با ابعاد بالا چالش‌های ریاضی زیادی را به همراه این فرصت که جنبه‌های بیشتری از اطلاعات نهفته را نمایش می‌دهند به وجود می‌آورند. یکی روش‌هایی که برای برخورد با مجموعه داده‌های با ابعاد بالا ارائه شدند روش کاهش ابعاد فضای جستجو هستند. Fodor [47] اشاره می‌کند که روش‌های آمار سنتی در مواجه با مسائل ابعاد بالا جوابگو نمی‌باشند، که به علت افزایش تعداد ملاحظات و بیشتر به خاطر افزایش در تعداد پارامترهایی همراه هر یک از این ملاحظات می‌باشد. او به جمع آوری اطلاعات از ابزارها قدیمی و جدید که برای کاهش بُعد مسائل ابعاد بالا را چاره گر هستند پرداخت.
نوآریا و بوکادوم [۴۴] به جای کاهش ابعاد فضای جستجو نویسندگان بر اکتشاف بهتر متمرکز شدند. در پیاده‌سازی‌هایی که بر اکتشاف بیشتر در فضای جستجو تاکید دارند مکانیزم کنترلی جدیدی برای بروز رسانی مکان ذره و یا مقدار دهی اولیه جمعیت ارائه می‌شود. Liu و سایرین [۴۸] یک استراتژی برای حرکت دادن ذرات تنبل که سبب ایستایی^[۳۶] و نهایتاً همگرایی زودرس^[۳۷] می‌شوند ارائه داده که این امر به اکتشاف بهتر و یافتن راه‌ حل ‌های مناسب‌تر منتج می‌شود. اگر سرعت ذره از یک مقدار مینیمم آستانه کمتر شود، یک سرعت جدید به وسیله مکانیزم آشفتگی به آن تخصیص داده می‌شود. مقدار مینیمم سرعت ذرات به وسیله‌ی یک کنترل گر منطق فازی تنظیم می‌شود. Coelho و سایرین [۴۹] یک روش ترکیبی ارائه دادند که در آن مؤلفه‎های PSO از یک توالی آشفته که توسط نگاشت Henon به وجود آمده استفاده می‌کنند. کاربرد توالی آشفته به جای توالی تصادفی یک استراتژی قدرتمند برای متنوع کردن و ایجاد جمعیت گوناگونی از ذرات است که کارایی PSO را به وسیله جلوگیری از همگرایی زودرس در بهینه محلی بهبود می‌دهد. محققان بسیاری PSO را با روش Simulated Annealing (SA) ترکیب کرده‌اند به گونه‌ای که PSO بهترین راه‌حل سراسری را یافته سپس به وسیله یک جستجو محلی با SA ارتقاء می‌یابد [۵۰-۵۲].
نوآریا و بوکادوم [۴۵] مکانیزم‌های محدودیت و پراکندگی باد بکار برده شدند. مکانیزم محدودیت به وسیله مقید کردن تغییرات در یک بازه محدود عمل می‌کند. به این صورت که مؤلفه k ام از فضای N بُعدی مکان ذره i به صورت معادله (۳-۶) مقید می‌شود:
(۲-۱۵)
مکانیزم دومی که به عنوان یک فرایند جستجوی آشفته شرح داده شده، پراکندگی به وسیله باد است. سرعت و جهت باد برای مدل کردن فضای جستجو تعریف شده‌اند. معادله به روز رسانی سرعت باد به صورت زیر در می‌آید.
(۲-۱۶)
که در آن vw سرعت باد، v_op عامل جهت مخالف و برابر ۱- و v_su عامل جهت موافق و برابر با ۱ است. سرعت باد دو اثر می‌تواند داشته باشد: حرکت یک ذره را می‌تواند برعکس جهت فعلی نماید و یا آن را تقویت کند. اثر مخالف سرعت ذره را در رسیدن به بهترین ذره کاهش می‌دهد و اثر موافق سرعت ذره را در رسیدن به آن افزایش می‌دهد. هر ذره به صورت جداگانه به روز می‌شود. این امر سبب ایجاد نیروهای پویای متفاوتی در فضای مسأله می‌شود. اگر مقادیر اثر موافق و مخالف سرعت‌های باد یکسان باشد، یک اتمسفر ایستا مدل می‌شود. معادله اصلاح شده‌ی فضای مکان N بُعدی خواهد بود:
(۲-۱۷)
وقتی مکانیزم محدودیت را با معادله به روز رسانی مکان ذره را با مکانیزم پراکندگی باد ادغام کنیم به جای معادله (۳-۶) خواهیم داشت:
(۲-۱۸)
مقادیر اولیه سرعت و جهش باد نقش مهمی را در همگرایی نهایی ذرات به راه‌حل بهینه بازی می‌کنند.

۲-۵-۲-۲- مشکل همبستگی میان داده‌ها

در انجام دسته‌بندی داشتن داده‌ها ورودی ناهمگن شامل مخلوطی از پارامترهای گسسته و پیوسته عددی^[۳۸] و پارامترهای اسمی^[۳۹] بسیار رخ می‌دهد. به عنوان مثال وقتی سیستم دسته‌بند در یک بیمارستان می‌خواهد افراد مراجعه کننده را به گروه‌های پیش شناسی و تشخیص (سالم و بیمار) تقسیم کند، تصمیم گیری در مورد این که آن‌ها را بپذیرد یا سرپایی درمان کند به شاخص‌های پیوسته (مانند درجه حرارت بدن، سطح اشباع اکسیژن و…)، شاخص‌های اسمی (مانند وجود یا نبود بعضی از نشانه‌های بیماری، جنسی بیمار و…) و مقیاس ترتیبی^[۴۰] بستگی دارد.
هنگامی با چنین داده‌های ناهمسانی سر و کار داریم، دسته‌بندهای معمولی یک مرحله کد نویسی اولیه برای نگاشت مقادیر غیر عددی به عدد صحیح انجام می‌دهند. در این رابطه آن‌ها با دو مشکل مواجه می‌شوند: چگونه یک رابطه ترتیبی وزن‌های واقعی برای مقادیر متفاوت را در داده‌های تغییر شکل یافته توجیه و برقرار می‌کند. همچنین، چگونه سمت‌گیری^[۴۱] دانش ارائه شده به علت یک روش کدگذاری دلخواه که اهمیت نسبی مقادیر غیر عددی را نادیده می‌گیرد مورد ملاحظه قرار می‌دهد. نوآریا و بوکادوم [۵۳] روشی برای اجتناب از مشکلات قبلی ارائه شد که به جای کد نویسی محض از ترجمه استفاده می‌کند. مکانیزم ترجمه^[۴۲] (تفسیر) به طور ذاتی وزن‌های معنایی را تولید کرده و به آسانی در روش‌های دسته‌بندی مکاشفه‌ای تلفیق می‌شود.
چندین مدل بر پایه‌ی گسسته سازی الگوریتم بهینه‌سازی ازدحام ذرات پیشنهاد شده که برای حل مسائل گسسته کاربرد دارند. در این روش‌ها ذرات نمی‌توانند به صورت پیوسته پرواز کنند.
در روش کدگذاری دودویی PSO یک مدل تغییر یافته از الگوریتم PSO برای حل مسائل که راه‌حل آن‌ها از عنصرهای دودویی تشکیل شده بودند به وسیله ابداع کنندگان PSO ارائه شد [۵۴].
الگوریتم اصلاح شده مکانیزم به روز رسانی مکان بردار ذره که در معادله (۲-۱۰) آمده را یک معادله جدید که مؤلفه‌های بردار مکان آن به صورت زیر خواهد بود:
x_ij =
۱ if rand() < S(v_ij)
۰ otherwise
(۲-۱۹)
در معادله (۲-۱۹) v_ij سرعت ذره i ام در مؤلفه j ام است که از طریق معادله (۲-۱۱) به دست آمده و S(v_ij) یک تابع سیگموئید است. از آنجایی که ذرات نمی‌توانند در فضای گسسته به صورت پیوسته پرواز کنند، مفهوم پارامتر سرعت به احتمال بخش متناظر راه‌حل اشاره می‌کند که می‌تواند مقدار ۱ یا ۰ بگیرد.
در روش گرد کردن مقادیر مکان مقدار مکان به نزدیک‌ترین عدد صحیح گرد می‌شود و به این ترتیب راه‌حل گسسته تولید می‌شود [۵۵]. این روش از همگرایی آهسته مقادیر سرعت کم (کمتر از ۰٫۵) رنج می‌برد زیرا این سرعت‌ها به صفر گرد می‌شوند. بنابراین اگر سرعت ذره خیلی پایین باشد ذره در دور مربوطه حرکت نخواهد کرد. باید در نظر داشت که مسائل بهینه‌سازی پیچیده به هزاران تکرار برای کامل شدن نیاز دارند و وقوع سرعت‌های پایین می‌تواند به طور قابل ملاحظه‌ای سرعت فرایند بهینه‌سازی را کاهش دهد.
الگوریتم دیگری که نوعی بهینه‌سازی ازدحام ذرات گسسته DPSO^[43] محسوب می‌شود الگوریتم JPSO^[44] است [۵۶, ۵۷]. این روش چیزی به نام سرعت در نظر نمی‌گیرد که این را به علت بی معنی بودن مفهوم سرعت پیوسته در فضای گسسته می‌داند. اما جذب توسط بهترین ذرات همچنان وجود دارد. JPSO جمعیتی از ذرات را که موقعیتشان درون فضای حالت توسط پرش از یک مکان به مکان (راه‌حل) دیگر تغییر کرده و تکامل می‌یابد. در هر تکرار هر ذره یک رفتار تصادفی را برای پریدن به مکان جدید بروز می‌دهد به طوری که یک جذب کننده نیز بر این رفتار اثر گذاشته و آن را هدایت می‌کند. الگوریتم سه جذب کننده را برای حرکت ذره i ام در نظر می‌گیرد: بهترین موقعیت شخصی ذره y_i (t)، بهترین موقعیت همسایگان اجتماعی و بهترین موقعیت جمعی  که کل ذرات تا آن لحظه کشف نموده‌اند. نویسندگان نشان دادند که JPSO توانایی بدست آوردن پاسخ‌های مناسب برای مجموعه داده‌های بزرگ را دارد.
روش تفسیر مکانی بر مبنای نوع ویژگی هنگامی که PSO را برای مجموعه داده با ویژگی‌های ناهمسان به کار می‌بریم کاربرد دارد. مطالعات پیشین اکثراً بر مدل نمودن PSO به صورت مقادیر پیوسته یا گسسته اشاره داشتند. گسسته سازی و نگاشت مقادیر اسمی و غیر عددی به عدد صحیح در مواردی مانند مواجه با ویژگی‌های اسمی می‌تواند مشکلات بالقوه‌ای را ایجاد کند. اما همان‌طور که اشاره شد در این رابطه‌ها با دو مشکل به وقوع می‌پیوندد: چگونه یک رابطه ترتیبی وزن‌های واقعی برای مقادیر متفاوت را در داده‌های تغییر شکل یافته توجیه و برقرار می‌کند. همچنین، چگونه سمت‌گیری^[۴۵] دانش ارائه شده به علت یک روش کدگذاری دلخواه که اهمیت نسبی مقادیر غیر عددی را نادیده می‌گیرد مورد ملاحظه قرار می‌گیرد و یک نمایش یکدست ارائه می‌شود.
نوآریا^[۴۶] و بوکادوم^[۴۷] [۵۸] یک الگوریتم PSO با یک مکانیزم تفسیر مکانی بر مبنای نوع ویژگی برای بازیابی مواردی که ویژگی‌های ناهمسان در داده‌ها موجود بود ارائه کردند. نوآریا^[۴۸] و بوکادوم^[۴۹] [۵۳] روش دیگری دوباره برای دسته‌بندی بر روی مجموعه داده‌های مختلفی آزمایش شد. این روش به وسیله تفسیر به جای کد نویسی به طور ذاتی از بسیاری از مشکلات قبلی دوری می‌گزیند. مکانیزم ترجمه به طور ذاتی وزن‌های معنایی را تولید کرده و به آسانی در روش‌های دسته‌بندی مکاشفه‌ای تلفیق می‌شود. این روش می‌تواند به طور یکسان در کارهای دسته‌بندی با انواع داده‌های ورودی اسمی، پیوسته و گسسته به کار رود. ایده اصلی به این صورت است که با یک الگوریتم PSO پیوسته شروع به کار کنیم و از مکانیزم‌هایی برای ترجمه و تفسیر مکان ذرات به صورت مناسب استفاده کرد؛ لذا دو فضا مورد بررسی قرار می‌گیرد: یک فضای جستجو مانند PSO استاندارد که ذرات در مختصات پیوسته تکامل می‌یابند و یک فضای تفسیر که در مواردی که بردارهای ورودی با مقادیر عددی پیوسته یا گسسته و یا مؤلفه‌های اسمی بیان شده‌اند منعکس کننده واقعیات است. هنگامی ذره در امتداد محورهای پیوسته در فضای جستجو تکامل می‌یابد، موقعیت‌های مکانی آن به عبارت‌های توصیف گر^[۵۰] (برای صفات) از انواع مختلف ترجمه می‌شوند. یک نگاشت معنایی بین این دو فضا اجازه انتقال از یک فضا به دیگر را می‌دهد. در نگاشت معنایی مجموعه‌ای از مکانیزم‌های تفسیر (ترجمه) تضمین می‌کنند برای مقادیر پیوسته در فضای اول مقادیر پیوسته، گسسته و یا اسمی در فضای دوم وجود خواهد داشت.
در نتیجه‌ی وجود مکانیزم‌های ترجمه الگوریتم PSO همچنان کارکرد خود را به عنوان یک روش پیوسته حفظ کرده است و تنها تفسیر متفاوتی از موقعیت‌های مکانی ارائه شده است. تغییرات در درجه اول برای ارزیابی تابع برازش که معنای فضای تفسیر را بیان می‌کند اتفاق می‌افتد. سرعت، موقعیت و اینرسی همچنان در فضای جستجوی پیوسته تکامل می‌یابند و تنها تابع برازش با مقادیر ترجمه شده صفات ناهمسان در فضای تفسیر ارزیابی می‌شود. به بیان دیگر جستجو در فضای جستجو و مقایسه در فضای تفسیر انجام می‌شوند.

۲-۵-۳- گونه‌های مختلف PSO

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

۲-۵-۳-۱- بهینه‌سازی ازدحام ذرات مبتنی بر شبکه‌های جمعی

انواع پیاده‌سازی PSO مبتنی بر شبکه‌های جمعی میان ذرات شیوه محاسبه بهترین خاطره شخصی و بهترین مکان‌های موجود در همسایگی را تغییر می‌دهد و یک توپولوژی اجتماعی جدید را معرفی می‌کند.

۲-۵-۳-۱-۱- همسایگی مبتنی بر فاصله فضایی

Suhanthan فاصله اقلیدسی میان ذرات را به عنوان همسایگی میان آن‌ها پیشنهاد داد [۳۶]. برای همسایگی به اندازه n_N، همسایگی ذره i شامل n_N ذراتی می‌شود که به ذره i نزدیک‌تر هستند. محاسبه فضای همسایگی نیازمند مشخص کردن فاصله اقلیدسی میان تمام ذرات در هر دور است، که مسلماً پیچیدگی محاسباتی الگوریتم جستجو را بسیار بالا می‌برد. اگر n_t دور از الگوریتم اجرا شده باشد محاسبه فضای همسایگی دارای هزینه محاسباتی O(n_tn_s²) می‌باشد. همچنین تعیین همسایگی بر اساس فاصله این فایده را دارد که تغییرات در همسایگی به صورت پویا در هر دور حساب می‌شود.
یک نوع متفاوت از پیاده‌سازی فضای همسایگی به نام همسایگی فضایی مبتنی بر برازندگی^[۵۱] توسط Braendler و Hendtlass ارائه شد [۵۹]، که در آن ذرات به سمت ذراتی از همسایگی حرکت می‌کنند که پاسخ مناسبی را پیدا کرده‌اند.

۲-۵-۳-۱-۲- همسایگی فزاینده

همان‌طور که قبلاً مطرح کردیم چنانچه شبکه جمعی میان ذرات دارای اتصالات داخلی کمتری باشند دیرتر همگرا می‌شوند، که باعث می‌شود اکتشاف بیشتری در فضای جستجو انجام شود. یک توپولوژی ستاره مانند با اتصالات داخلی کامل سریع‌تر همگرا می‌شود اما به قیمت نادیده گرفتن بخش‌هایی از فضای جستجو. برای اینکه بتوان از فواید اکتشاف بیشتر و سرعت همگرایی بالاتر بهره ببریم Suhanthan این دو ایده را با هم ترکیب نمود [۳۶].
جستجو با اندازه همسایگی n_N=2 برای تعیین بهترین موقعیت در همسایگی آغاز می‌شود. اندازه همسایگی با افزایش تکرار بیشتر می‌شود تا این که همسایگی تمام جمعیت را در بر بگیرد (n_N=n_s). همسایگی فزاینده اجازه می‌دهد در تکرارهای اولیه اکتشاف بهتری در فضای جستجو داشته باشیم و در مراحل پایانی سرعت همگرایی را افزایش دهیم.

۲-۵-۳-۱-۳- بهینه‌سازی ازدحام ذرات کاملاً آگاه (FIPS^[52])

همان‌طور که در معادله سرعت استاندارد (۲-۱۱) آمده موقعیت جدید هر ذره به وسیله خود ذره و بهترین ذره‌ای که در همسایگی‌اش قرار دارد مورد تأثیر قرار می‌گیرد. Kennedy و Mendes مشاهده کردند گونه‌های انسانی به وسیله تنها یک فرد مورد تأثیر قرار نمی‌گیرند، بلکه عموماً مجموع کلی همسایگان بر آن‌ها اثر خواهند گذاشت [۶۰].
بر مبنای این اصل معادله سرعت در FIPS به گونه‌ای تغییر می‌کند که هر ذره توسط نتایج مطلوب مجموع همسایگانش و نه کارایی تنها یک ذره تحت تأثیر قرار می‌گیرد. نقطه‌ی ضعف FIPS این است که این حقیقت را که اثر چند ذره ممکن تأثیر یکدیگر را خنثی کنند را در نظر نمی‌گیرد. مثلاً فرض کنید اگر دو همسایه به ترتیب به اندازه a و –a در معادله سرعت تأثیر داشته باشند، جمع آن‌ها برابر صفر می‌شود.