تکنیک های بهینه سازی

2-1-مقدمه

در زندگی روزمره، تمامی ما با برخی تصمیم گیری هایی مواجه شده ایم. معمولاً، برای تصمیم بهتر تلاش می کنیم. اگر فردی کالایی می خرد، او برای خرید بهترین کیفیت با حداقل هزینه تلاش می کند. این نوع از تصمیم گیری به عنوان مسائل بهینه سازی دسته بندی می شوند که در آن هدف یافتن بهترین راه حل است؛ طوری که بهینه می تواند کمترین یا بیشترین باشد.

هدف این فصل، مرور خلاصه ی اساس مسائل بهینه سازی می باشد. بدیهی است که جزئیات فراتر از محدوده ی این کتاب است و باید از منابع موجود دنبال گردند. به هر حال، یک مثال ساده مطرح شده و با استفاده از برخی روش ها حل شده است؛ همانطور که در پیوست B بیان گردیده است.

این مقاله توسط شرکت برای بهره مندی دانشجویان از مقالات بروز دنیا ترجمه شده است . 

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

2-2- بیان مسئله

بسیاری از مسائل کاربردی و برنامه ریزی از سه مرحله ی اصلی تشکیل شده است:

• تعریف

• مدل سازی

• الگوریتم

در زیربخش های مربوطه، آن ها را با جزئیات بیان می کنیم.

2-2-1-تعریف مسئله

در هر مسئله بهینه سازی، تصمیم گیرنده باید مطابق آیتم های زیر تصمیم بگیرد

• تصمیم (مستقل) و متغیرهای وابسته

• توابع محدودیت

• توابع هدف

2-2-1-1-تصمیم و متغیرهای وابسته

متغیرهای تصمیم، متغیرهای مستقل هستند. تصمیم گیرنده باید مقادیر بهینه را تعیین کند و بر اساس آن ، سایر متغیرها (وابسته) می تواند تعین شود. به عنوان مثال، در یک مسئله برنامه ریزی تولید بهینه، تولید برق فعال نیروگاه برق می تواند متغیرهای تصمیم باشد. متغیرهای وابسته می تواند مصرف سوخت کل، افت سیستم، و … باشد. که می تواند به محض تعیین متغیرهای تصمیم گیری محاسبه گردد. در مسئله تخصیص خازن، تمامی جایگیری ها و سایزبندی بانک های خازنی، متغیرهای تصمیم گیری هستند ، در حالی که متغیرهای وابسته می تواند ولتاژ اتوبوس، افت های سیستم و … باشد.

یک مسئله متغیر n-تصمیم منجر به یک فضای راه حل n-بعدی می شود که در آن هر نقطه در بین آن فضا می تواند یک راه حل باشد. یک مورد دو بعدی در شکل 2-1 نشان داده شده است.

2-2-1-2-توابع محدودیت

در مسئله بهینه سازی زندگی واقعی، برخی محدودیت ها ممکن است برای فضای راه حل اعمال شود. این موارد نوعاً تکنیکی، اقتصادی، محیطی و محدودیت های مشابه هستند که محددویت نامیده می شوند که به طور مستقیم و غیر مستقیم فضای راه حل را به نواحی قابل پذیرش (ممکن) و غیرقابل پذیرش (غیر ممکن) تقسیم می کند. تصمیم گیرنده باید نقطه ی راه حل را در ناحیه ی ممکن پیدا کند. به عنوان مثال، در مسئله ی برنامه ریزی تولید بهینه ، تولید برق فعال نیروگاه برق، باید بین مقادیر کمینه و بیشینه ی مورد انتظار باشد؛ یا تولید کل نیروگاه باید بارگیری کل و یک ذخیره ویژه را قانع سازد. در مسئله تخصیص خازن، محدودیت های تکنیکی ممکن است تعداد بیشینه ی بانک های خازنی باشد که ممکن است برای bus ویژه بکار گرفته شده باشد. یک محدودیت اقتصادی ممکن است روی هزینه کل سرمایه گذاری عملی باشد که نمی تواند نقض شود. شیوه ی رفتار محدودیت ها در دو بعد در شکل 2-2 نشان داده شده است.

2-2-1-3- توابع هدف

از بین نقاط متعدد در ناحیه ی ممکن مسئله، تصمیم گیرنده باید مطلوبترین را انتخاب کند. مطلوبترین باید، به هرحال، باید به نحوی تعریف شده باشد. به عنوان مثال، در یک کلاس درس، اگر اخلاق ملاک اصلی باشد، یک شاگرد را به عنوان بهترین انتخاب می کند. اگر اشتیاق مشاهده شود (ملاک باشد)، باید دیگری را انتخاب کند. در حقیقت، یک تابع هدفمند، تابعی به جای متغیرهای تصمیم گیری است که به وسیله ی آن تصمیم گیرنده راه حل های مطلوب را نمایش می دهد. در شکل 2-3، اگر تابع هدفمند برای بیشینه کردن x1 تعریف شده باشد، راه حل در پایان نقطه ی A، تمام می شود، در حالی که اگر  کمینه کردن x2 تابع هدف باشد، نقطه B، راه حل نهایی خواهد بود. در بک مسئله برنامه ریزی تولید بهینه، تابع هدف ممکن است انتخاب شده باشد تا هزینه کل سوخت کمینه گردد. در مسئله جایگیری خازن، تابع هدف ممکن است هزینه یا افت سیستم یا هر دو را سرمایه گذاری کند (تا کمینه گردند). مسئله طوری در نظر گرفته می شود که تک-هدف باشد ، یا فقط یک تابع هدف بهینه شده باشد. که در مقابل مسائل بهینه سازی چند-هدفی قرار می گیرد که در آن چندین تابع به طور همزمان بهینه شده اند.

در عمل، در مسائل بهینه سازی، ممکن است چندین نقطه ی مینیمم و ماکزیمم وجود داشته باشد. برای مثال، مورد نشان داده شده در شکل 2-4 را در نظر بگیرید که در آن تابع هدف، تنها تابع x1 و بیشینه شده باشد. همانطور که نشان داده شده ، برخی محل های بهینه وجود دارد به این معنا که آنها در مجاورت نقاط نزدیک، بهینه هستند. از آن نقاط بهینه محلی، یکی بهینه ی سراسری می باشد.

2-2-2- مدل سازی مسئله

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

که در آن x، متغیرهای تصمیم گیری، C(x) تابع هدف و g(x) ≤ b محدودیت نابرابری می باشد.

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

C و g ممکن است توابع پیوسته یا مجزای متغیرهای تصمیم گیری در یک فرم صریح یا ضمنی، خطی یا غیر خطی باشند. بر اساس آنها، مسئله ی بهینه سازی به طور مناسب نامگذاری شده است. به عنوان مثال، مسئله ی بهینه سازی خطی عدد صحیح، مسئله ای است که در آن C و g توابع خطی متغیرهای تصمیم گیری عدد صحیح هستند.

در حالت کلی

• ماکزیمم کردن C برابر با مینیمم کردن (-C) می باشد.
• می توانیم برابری محدودیت را f(x) بنامیم تا ان را از g(x) جدا کنیم.
• ممکن است بیش از یک f(x) یا g(x) داشته باشیم.
• ممکن است بیش از یک متغیر مستقل x داشته باشیم. (در عوض، یک محور از x).

مسئله بهینه سازی کلی می تواند به صورت زیر باشد

2-3-الگوریتم های راه حل، ریاضیات در مقابل تکنیک های ابتکاری

یک مسئله بهینه سازی محدود شده که با (2-2)، (2-3) و (2-4) نشان داده شده ممکن است به برخی تکنیک های بهینه سازی حل گردد. این تکنیک ها ممکن است عموما به صورت ریاضی یا ابتکاری دسته بندی گردند. هر دو در منابع سیستم های قدرت (برق) مورد توجه بوده اند. این امر در زیر بخش مربوطه مرور شده است.

2-3-1-الگوریتم های ریاضی

تکنیک بهینه سازی ریاضی ، مسئله را به صورت ریاضیاتی فرموله می کند که از (2-2) تا (2-4) نشان داده شده است. تابع هدف و/یا محدودیت غیر خطی هستند ، مسئله ی حاصل به صورت مسئله بهینه سازی غیر خطی (NLP) طراحی شده است. مورد ویژه ی NLP برنامه ریزی مربعی است که در ان تابع هدف تابع درجه دوم X می باشد.  اگر هر دو تابع هدف و محدودیت توابع خطی X باشند، مسئله به صورت یک مسئله ی برنامه ریزی خطی (LP) طراحی می شود. طبقه بندی دیگر می تواند بر پایه ی طبیعت متغیرها تشخیص داده شود. برای مثال، اگر X از نوع عدد صحیح باشد، مسئله به صورت برنامه ریزی عدد صحیح (IP) نشان داده می شود. انواع مختلط مانند MILP،( برنامه ریزی مختلط واقعی عدد صحیح)  می تواند وجود داشته باشد که در آن متغیرها میتوانند واقعی و عددد صحیح باشند، مسئله اغلب از نوع LP می باشد.

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

هیچ  طبقه بندی محدود و ثابتی از الگوریتم های ریاضی وجود ندارد. در اینجا قصد نداریم که آن ها را با جزئیات مورد بحث قرار دهیم. در عوض، ما قصد داریم برخی موضوعاتی را معرفی کنیم که در این کتاب بسیار مورد علاقه بوده و ممکن است در مبحث برنامه ریزی سیستم های قدرت(برق) کاربردی باشد. برخی موضوعات، مانند تئوری game که برای دیگر مباحث سیستم های قدرت مورد علاقه است (مانند آنالیز بازار سیستم های قدرت) در اینجا بیان نمی شوند.

2-3-1-1- روش های محاسبه

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

بر اساس محاسبات دیفرانسیل توسعه یافته برای یافتن نقاط بهینه  C(x) (بخش2-2 را ببینید)، روش ضریب لاگرانژ برای یافتن نقاط بهینه  گسترش یافته است. که محدودیت های برابر (2-3) ممکن است اعمال شود. اگر محدودیت های نابرابر (2-4) قابل کاربرد باشند، هنوز روش پایه ممکن است استفاده شود، به هرحال شرایط Kuhn-Tucker باشد مشاهده شود. در این مورد راه حل مستقیم نیست.

2-3-1-2- روش برنامه ریزی خطی (LP)

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

• به این حقیقت توجه کنید که هر مسئله ی LP میتواند به عنوان مسئله ی کمینه سازی قرار بگیرد؛ به موجب این حقیقت، که اکنون شرح داده شد، ماکزیمم سازی C(x) برابر با مینیمم سازی (-C(x)) می باشد.
• تمامی محدودیتها ممکن است در نوع برابری قرار گیرد. به موجب این حقیقت که هر محدودیت نابرابری از آنها که از عبارت زیر به دس می آید:

می تواند به محدودیت برابری تبدیل شود ، با عبارت

به ترتیب، _n+1´x و x´´_n+1 که متغیرهای نامنفی هستند، به عنوان متغیرهای مازاد شناخته می شوند.

• تمامی متغیرهای تصمیم گیری می توانند نامنفی در نظر گرفته شوند ، همانطور که هر xj ، در علامت نامحدود می تواند به صورت xj= x´j- x´´j  نوشته شود که

مشاهده می شود که xj ، بسته به اینکه x´´j  برابر ، مساوی یا کمتر از x´j است، می تواند منفی، صفر یا مثبت باشد. سپس، یک راه حل که  به عنوان روش simplex شناخته شده است، ابتدا در دهه ی 1940 ابداع شد، ممکن است برای حل مسئله استفاده شود.

استفاده از روش simplex به طور معمول نیازمند مقادیر زیادی از ذخایر کامپیوتر و زمان می باشد. روش revised simplex، یک روش تجدید نظر شده است که در آن زمان محاسباتی کمتر و فضای ذخیره ی کمتری نیاز است.

هنوز نوع دیگری از مسئله ی LP جذاب، تئوری دوگانگی می باشد. در حقیقت، همراه با هر مسئله ی LP، مسئله ی دوگانه، ممکن است فرموله شود. در بسیاری از موارد، راه حل مسئله ی LP، ممکن است بسیار راحت تر از مسئله ی دوگانه به دست آید.

اگر مسئله ی LP، ساختار ویژه دارد، اصل decomposition، ممکن است برای حل مسئله ای که در ان ذخیره ی کامپیوتری کمتری مورد نیاز است،  بکار گرفته شود. در این روش، مسئله می تواند به روش موثرتری حل گردد.

مشکلات حمل و نقل، از مسائل ویزه ی LP هستند که اغلب در عمل اتفاق می افتد. این مسائل می توانند با برخی الگوریتم ها حل شوند که از روش simplex بسیار موثرتر است.

2-3-1-3- روش برنامه ریزی غیر خطی (NLP)

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

قبل از پسشرفت بیشتر در مسئله ی NLP، باید دقت کنیم که بسیاری از مسائل عملی از نوع محدودیت هستند که در آن برخی توابع محددودیت باید پذیرفته شود. برای مسائل محدودیت، به هرحال، برخی الگوریتم ها روی اصل تبدیل مسائل به نوع نامحدود کار می کنند، ما در ابتدا برخی الگوریتمهای موجود را مسائل نامحدود روی بررسی می کنیم.

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

تمامی روش های بهینه سازی محدود، دارای طبیعت تکرار شونده هستند و از روش حل آزمایشی اولیه شروع می شوند، به صورت پلکانی در حالت زنجیره ای به سمت راه حل بهینه حرکت می کنند. روش گرادیان، در منابع سیستم های قدرت توجه بیشتری را جلب کرده است. برای مثال، در روش steepest descent، که به طور گسترده در منابع سیستم های قدرت استفاده می شود، محور گرادیان، برای محاسبه ی طول بهینه  پله در طول تحقیق استفاده می شود، بنابراین کارایی الگوریتم ماکزیمم می گردد.

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

به عنوان مثالی از روش مستقیم، روش تقریب محدودیت، تابع هدف، و محدودیت در برخی نقاط خطی شده اند. مسئله ی LP تقریب شده ی حاصل، با استفاده از تکنیک های LP حل شده است. راه حل حاصل، سپس برای ساختن مسئله ی LP جدید، استفاده شد. فرایند تا جایی که معیار همگرایی قانع کننده باشد، ادامه یافت.

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

2-3-1-4- روش برنامه ریزی دینامیک (DP)

برنامه ریزی دینامیک تکنیکی است که به طور گسترده در مطالعات سیستم های قدرت استفاده شده است. در حقیقت، یک تکنیک ریاضیاتی است که برای مسائل تصمیم گیری چندمرحله ای استفاده شد؛ در اصل در دهه ی 1950 توسعه پیدا کرد.

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

تمامی تابع هدف، در همه ی مراحل بهینه شده است. به طور نرمال تابعی از متغیرهای تصمیم گیری (xi) تمامی مراحل می باشد. حقیقت مهم آن است که نمی توان ار بهینه ی مرحله ی اول شروع کرد؛ و از جلو به سمت مرحله ی نهایی حرکت نماید. همانطور که ممکن است برخی همبستگی های بین مراحل وجود داشته باشد.

برای روشن سازی مسئله، اجازه دهید تا مثال سیستم قدرت را توضیح دهیم. در نظر بگیرید قصد داریم هزینه تولید سیستم قدرت در یک دوره ی 24 ساعته را مینیمم کنیم. برخی اطلاعات مطابق زیر است:

• چهار واحد تولید موجود است؛ هر یک ممکن است فعال یا غیر فعال باشد(بنابراین ترکیبهای متفاوتی امکانپذیر است، مانند 1111, 1101,1001,0011) .
• کارایی واحدها متفاوت است، بنابراین اگر بارگیری سیستم پایین باشد و گفته می شود دو واحد می تواند بارگیری را داشته باشند، باید از واحدهای با عملکرد بالاتر استفاده کنیم تا بارگیری فراهم شود.
• بارگیری در طول 24 ساعت تغییر می کند، آن را در هر ساعت تغییر دهید. (مرحله).

مسئله ی تصمیم گیری چندمرحله ای در حقیقت، تصمیم گیری در مورد واحدهایی است که باید در هر مرحله روشن باشد، بنابراین کل هزینه ی تولید در تمامی دوره ی 24 ساعته مینیمم شده است. باید توجه کنیم که اگر هیچ محدودیتی اعمال نشد، باید مسئله را در هر مرحله بهینه کنیم و آن را در تمامی مراحل جمع بببندیم. به عبارت دیگر، 24 مرحله ی منفرد مسائل بهینه باید، برای یافتن راه حل نهایی حل شوند.

فرض کنید که اه حل نهایی مانند شکل 2-5 باشد که در آن ترکیب واحد در هر مرحله نشان داده شده است.

همانطور که نشان داده شده، واحد 1 در ساعت 1 روشن، و واحد 2 در ساعت 3 خاموش است   و دوباره در ساعت 4روشن می باشد. اکنون چه جیزی اتفاق می افتد اگر یک محدودیت، برای بیان این حقیقت اعمال شود که واحد 1 خاموش شده و نمیتواند روشن شود مگر اینکه یک دوره ی 5 ساعته طی شود. بنابراین، راه حل های فوق کاربردی نیستند . اکنون ، چگونه می توانیم راه حل را بیابیم؟

می توان کنترل کرد که در هر مرحله، برای چهار واحد فوق، تعداد ترکیب ها 2⁴-1=15 می باشد. برای دوره ی 24 ساعته، تعداد ترکیب ها باید (15)²⁴ باشد. اگر تعداد واحدها 100 و تعداد مراحل 168(یک هفته) باشد، چه اتفاقی می افتد؟ تعداد کل ترکیب ها (2¹⁰⁰-1)¹⁶⁸! خواهد بود.

در تکنیک DP، مسئله ی تصمیم گیری چند مرحله ای به یک زنجیره از مسائل مرحله ای منفرد تجزیه شده، که به ترتیب حل شده است. تجزیه باید به این صورت انجام شود که راه حل بهینه مسئله ی اصلی بتواند از حل بهینه ی مسائل مرحله ای منفرد به دست آید.

2-3-1-5- روش برنامه ریزی عدد صحیح

در الگوریتم هایی که ا کنون بحث شد، هر متغیر تصمیم گیری، یک مقدار واقغی به خود می گیرد. اگر متغیرهای تصمیم گیری به گرفتن تنها یک عدد صحیح محدود شوند، چه اتفاقی می افتد؟برای مثال، اگر متغیر تصمیم گیری تعداد واحد های تولید باشد ، دریافت یک مقدار واقعی بی معنی است. الگوریتم بهینه سازی برای این دسته از مسائل، به عنوان روش IP دسته بندی می گردد.  اگر تمامی متغیرهای تصمیم گیری از نوع صحیح باشند، مسئله، به عنوان مسئله ی IP شناخته می شود. اگر برخی متغیرهای تصمیم گیری از نوع عدد صحیح باشند و برخی از نوع ناصحیح، مسئله به عنوان مسئله ی برنامه ریزی  عدد صحیح مختلط نامیده می شود.

بعلاوه، بر اساس طبیعت مسئله ی اصلی، هر دو روش برنامه ریزی خطی صحیح و برنامه ریزی خطی ناصحیح توسعه یافته اند. در نتیجه ، در منابع سیستم قدرت، برخی واژه ها مانند  MILP ظاهر شده اند.

2-3-2-الگوریتم های ابتکاری

بسیاری از الگوریتم های ریاضی، می تواند دستیابی به راه حل بهینه را تضمین نماید؛ در حالی که ضرورتاً دست یابی به بهینه ی سراسری را تضمین نمی کند. برای موارد ساده، بهینگی کلی ممکن است تنها به دست آید، کنترل شود یا تضمین گردد.

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

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

یک الگوریتم ساده ی ابتکاری، ممکن است بر اساس برخی انواع آنالیزهای حساس ابداع شده باشند. برای مثال، در مسئله ی جایگیری خازن، حساسیت تابع هدف، ممکن است با کاربرد بانک خازن در BUS تعیین شود. پس از انجام، خازن به BUS بسیار حساس افزوده می شود و فرایند به جای تابع هدف تا دست یابی به بیشترین بهبود، تکرار می شود.

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

• الگوریتم های ژنتیکی (GA)، بر اساس ژنتیک و تکامل

• روش شبیه سازی آنیلینگ (SA) بر مبنای برخی اصول ترمودینامیکی

• ازدحام ذرات(PS)، بر اساس حرکات پرندگان و ماهی ها

• تحقیق تابو (TS)، بر اساس پاسخ حافظه

• کلونی مورچه (AC)، بر مبنای اینکه مورچه ها چگونه رفتار می کنند.

تا کنون برخی تکنیک ها ذکر شده اند. به هرحال، ما بحث خود را در اینجا، روی الگوریتم های فوق محدود کرده ایم. خواننده ی علاقه مند باید منابع ذکر شده در انتهای این فصل را دنبال نماید.

2-3-2-1- الگوریتم ژنتیک

در طبیعت، هر گونه با یک محیط دارای چالش مواجه می شود و باید برای بیشترین احتمال بقا خود را مطابقت دهد. همانطور که زمان می گذرد، گونه های دارای ویژگی های بهتر، زنده می مانند. در حقیقت، شایسته ترین نوع، زنده مانده است. این نوع پدیده ها که در طبیعت اتفاق می افتد، اساس تکامل بر پایه ی GA است.

الگوریتم ژنتیکی عمدتا توسط Holland گسترش یافت. متغیرهای تصمیم گیری که یافت شدند به صورت کدبندی دوتایی، کدبندی مقدار واقعی یا کدبندی عدد صحیح، به فرم زنجیره ای از ژنها بودند. این زنجیره مسئله ی کروموزوم نامیده شد، که از مجموعه ای که افراد نامیده می شود، انتخاب شده است. تابع هدف، برای این کروموزوم، به عنوان مسئله ی تابع تناسب (سازگاری) محاسبه شده است. بعد از تنظیم جمعیت اولیه، انتخاب یک کروموزوم و محاسبه ی سازگاری آن، جمعیت بعدی تولید می شود؛ بر اساس شیوه ای که بعد از آن مسخص شده است. کروموزوم اولیه به عنوان والد و کروموزوم بازتولید شده فرزند نامیده می شود. همانطور که خواهیم دید، بازسازی منجر به کروموزوم هایی با مقادیر سازگاری بهتر خواهد شد. الگوریتک به سمت جلو پیش می رود تا جایی که هیچ بهبودی در تابع تناسب حاصل نشود.

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

• انتخاب، بر اساس ساختار کروموزوم تعریف شده است، جمعیتی از کروموزوم ها در ابتدا به صورت تصادفی یا هوشمندانه تولید شده است. ممکن است 3 تا100 کروموزوم در نظر گرفته شود. سپس، باید دو کروموزو را به عنوان والد برای فرآیندهای بیشتر انتخاب کنیم. مقدار مناسب، به عنوان معیار برای والدها انتخاب می شود.
• تقاطع. وقتی والدها انتخب می شوند باید توالی جدید فرزندان، از طریق دو نوع اپراتور ایجاد کنیم. کراس اور، روی اصل تبادل مقادیر بعد از یک موقعیت ویژه کار می کند. برای مثال، A و B، دو کروموزوم اولیه ی آنتخاب شده هستند:

و اپراتور کراس اوور در موقعیت 6 اعمال می شود، فرزندان حاصل چنین به نظر می  رسند:

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

• موتاسیون (جهش). یک اشکال ذاتی اپراتور کراس اوور این حقیقت است که در برخی موقعیت های ویژه، مقدار ژن ممکن است در کل تغییر نکند. برای دوری از این مسئله، اپراتور موتاسیون تلاش می کند تا مقدار ژن را به طور تصادفی از 1 تا 0 و بالعکس تغییر دهد. باید ذکر کنیم که ، به هر حال، که این به ندرت اتفاق می افتد.

ما ذکر کردیم که اپراتورهایی که در وفق ذکر شد، انواع ساده هستند. در عمل، اپراتورهای بسیار پیچیده ای برای بهبودعملکرد  GA گسترش یافته اند. در حال حاضر، GA توجه بسیاری را در منابع سیستم قدرت به خود جلب کرده است.

2-3-2-2- آنیلینگ شبیه سازی شده

انیلینگ شبیه سازی شده یک الگوریتم انعطاف پذیر در ارتباط با مسائل بهینه سازی ترکیبی می باشد. ممکن است برای مسائل مختلط، شامل توابع غیرمشتق پذیر، ناپیوسته و non-convex بکار گرفته شود.

آنیلینگ یک فرایند طبیعی  سرد کردن ماده ی مذاب، از دمای بالا می باشد. اگر فرایند سرد کردن، اگر در شرایط تعادل گرمایی انجام شودف آنیلینگ منجر به تشکیل کریستال ها می گردد. تشکیل یک کریستال کامل، برابر با حالت مینیم سازی انرژی است.

اولین بار اصول ذکر شده در فوق ، در دهه ی 1980، به عنوان الگوریتم در حل مسائل بهینه سازی ظاهر شدند. باید توجه شود که تطابق بین حالت فیزیکی ماده و فضای محلول یک مسئله بهینه سازی تعریف شود. انرژی ازاد ماده ممکن است به تابع هدف مسئله ی بهینه سازی مرتبط باشد.

قبل از پیشروی بیشتر، ابتدا باید الگوریتم متروپلی را به عنوان اساس الگوریتم SA  بحث کنیم.

• الگوریتم متروپلی. ذراتی که ماده را تشکیل می دهند، مطابق احتمال توزیع و بر اساس دمای(T) آنها ، دارای سطوح مختلفی از انرژی هستند.الگوریتم متروپلی روی اصل تولید یک حالت جدید Sj از حالت اولیه ی Si با انرژی Ei کار می کند. این حالت جدید، با یک مکانیسم متشکل از کمترین اختلال در حالت اصلی، تولید شده است. اختلال، در حقیقت، با حرکت یکی از اصول انتخابی با روش مونت کارلو به دست آمده است.
• برای انرژی حالت جدید، Ej(پیدا شده با احتمال)، اختلاف بین Ej-Ei، کنترل می شود تا کمتر یا برابر با صفر، برای پذیرش حالت جدید Sj باشد. اگر این اختلاف مثبت باشد، هنوز Sj قابل قبول است، اما با احتمال داده شده ی

که T  دمای مواد و KB ثابت بولتزمن می باشد. فرایند داده شده در فوق، به طور نرمال نیازمند مقدار زیادی حالات انتقال در دست یابی به حالتی با کمترین سطح انرژِ می باشد.

اصول فوق، در حل مسائل بهینه سازی پیگیری شده اند. SA اساساً از دو مکانیسم اصلی تشکیل شده است. یکی تولید جایگزین ها (حالتها) و دیگری قانون پذیرش می باشد. در ابتدا، برای دمای T0، توالی کنفیگوراسیون (N0) تولید شده است. سپس، کنفیگوراسیون اولیه ی Si، انتخاب شده است.  Tk پارامتر کنترل می باشد. در ابتدا، مقدار T زیاد است. سپس بر اساس یک طرح خنک سازی کاهش می یابد. معیار مورد قبول، همان است که در الگوریتم متروپلی عنوان شد.

دمای اولیهT0، تعداد انتقالاتی که در هر سطح دمایی انجام شد (Nk)، دمای نهایی Tf، (به عنوان معیار توقف کننده)، و توالی خنک سازی،(T_k+1 = g (T_k)* T_k ، که g(T_k) تابعی است که دما را کنترل می کند)، چهار پارامتر اصلی SA هستند. تعیین مناسب پارامترهای فوق در منابع مورد توجه بوده اند.

2-3-2-3-ازدحام ذرات

برخی موجودات طبیعی مانند ماه ها و پرندگان به صورت گروهی رفتار می کنند. هر  مختصات فردی حرکت آنها با دیگران به این صورت است که با دیگری برخورد نمی کند، به سمت مقصد حرکت می کند و به سمت مرکز گروه حرکت می کند (ازدحام).

اواسط دهه ی 1990 بود که ایده ی اصلی PS به عنوان الگوریتم بهینه فرموله شد.

مشخصات هر فرد (که عامل نامیده می شود) با موقعیت آن در فضای دو بعدی (x و y) و محور سرعت آن (Vx و Vy) نشان داده می شود. هر عامل حرکت خود به سوی مقضد را بهینه می کند. با این کار، ردیابی می کند:

• بهترین مقدار تابع هدف که تا کنون به دست آمده است (که pbest نامیده می شود).
• بهترین مقدار تابع هددف که دیگر عوامل تا کنون به دست آمده اند (که gbest نامیده می شود).

بنابراین، عامل ، موقعیت خود را اصلاح می کند، با توجه به

• موقعیت فعلی آن

• سرعت فعلی آن

• فاصله ی بین موقعیت فعلی با pbest و gbest.

به زبان ریاضی، موقعیت جدید یک عامل i، در دنباله ی K+1 (s_i^k+1) می تواند از موقعیت فعلی(تکرار k)  آن (s_i^k) تعیین شود. دانستن سرعت آن در K+1 (V_i^k+1)*(v_i^k+1) می تواند چنین تعیین شود:

که w، وزن، C1 و C2 ضرایب وزنی و rand1 , rand2، دو شماره ی تصادفی بین 0 و 1 می باشند.

عبارت اول منجر به حرکت عامل در جهتی مشابه قبلی می شود ، همانطور که منجر به ایجاد فضای جستجوی جدید می گردد. این دلیل آن است که چرا w به نام ضریب تنوع نامیده می شود. معمولا به صورت زیر تعریف می شود:

wˉ  و w_– به ترتیب 9/0 و 4/0 انتخاب می شوند. با (12-2) ، در ابتدا تنوع دارای وزن زیادی است و به سمت انتهای فرایند تحقیق کاهش می یابد. به عبارت دیگر، عبارات دوم و سوم (11-2) منجر به تشدید می گردند. C1 و C2 نوعا 2 انتخاب می شوند. مراحل درگیر در الگوریتم بهینه سازی PS میتواند به عنوان

• ایجاد شرایط اولیه برای هر عامل

• ارزیابی نقاط تحقیق هر عامل

• اصلاح هر نقطه ی تحقیق

شرح داده شود.

این فرایند برای اعداد ماکزیمم دنباله تکرار می شود.

باید ذکر شود که، برخی متغیرها ی روش بهینه سازی PS،  تا کنون برای شمارش برخی بهینه سازی ترکیبی عملی توسعه یافته اند.

2-3-2-4-تحقیق تابو

تابو، ممنوعیت در تحقیق یا بررسی را معنی می دهد. برخلاف دیگر روش های ترکیبی، TS به پدیده های فیزیکی مرتبط نیست. ابتدا دراوایل دهه ی 1980 مطرح شد. یک روش تکراری می باشد که از یک راه حل اولیه شروع می شود و تمایل دارد تا به سمت فضای حل جدید در یک شیوه ی تهاجمی یا حریص نسبت به GA یا SA حرکت نماید. همسایگی، که از آن راه حل/حرکت بعدی انتخاب می شود، با دسته بندی برخی حرکات مانند تابو اصلاح می شود، بقیه مطلوب هستند.

در هر دنباله ی الگوریتم، یک ساختار همسایه، تعریف شده است؛ یک حرکت، سپس برای بهترین پیکربندی ایجاد می شوود. برای گریز از نقاط بهینه ی محلی، برخی انتقالات به پیکربندی ها با هزینه ی بالاتر، مجاز می باشند.  مشابه با الگوریتم PS، با استفاده از تشدید و تنوع منجر به اکتشاف بسیار جامع نواحی جذاب می شوند و در زمان مشابه، به سمت نواحی دیده نشده ی قبلی حرکت می کند. این به دوری از، به دام افتادن در نقاط بهینه کمک می کند.

مراحل درگیر در الگوریتم بهینه سازی TS می تواند به صورت زیر خلاصه شود:

1) ایجاد راه حل اولیه

2)انتخاب حرکت

3)به روز رسانی راه حل. راه حل بعدی از لیست همسایه ها انتخاب می شود  که به عنوان مطلوب (داوطلب) یا غیر تابو در نظر گرفته می  شود و برای هر یک تابع هدف بهینه است.

فرایند بر اساس هر قانون توقف پیشنهادی، تکرار می شود. برخلاف دیگر الگوریتم های ابتکاری، زمینه ی  تئوری کافی برای ادامه ی TS به سمت یک مسئله ی عملی در دست وجود ندارد و کاربران مجبورند به تجارب عملی  خود متوسل شوند.

2-3-2-5-کلونی مورچه

تکنیک بهینه سازی AC،  یک تکنیک بهینه سازی ترکیبی است، که در ابتدا در اوایل دهه ی 1990 توسعه یافت. که بر مبنای رفتار حشرات، به ویژه مورچه ها پایه گذاری شده است.

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

دانشمندان کشف کرده اند که ابزار اصلی این پدیده، فرمون است که به عنوان رسانه ی ارتباطی اساسی بین افراد استفاده می شود.

به محض راه رفتن، هر مورچه یک ماده ی شیمیایی منتشر می کند، که فرومون نامیده می شود، که روی زمین باقی می ماند. در ابتدا، تمامی مورچه ها، به صورت تصادفی، برای یافتن غذا حرکت می کنند. اگر در نظر گرفته شوند که سرعت مشابهی دارند، هر یک که غذا را سریعتر یافت ( به  عبارتی با مسافت کوتاهتر) سریع به لانه بر می گردد و فرومون منتشر می کند تا برگردند. مسیر پر از فرومون می گردد. مورچه های دیگر، سریع آن را به عنوان یک مسیر امیدبخش تشخیص می دهند و همه ان را دنبال می کنند. بر اساس فوق، برخی الگوریتم های AC، توسعه یافته اند. اساساً، مراحل به صورت زیر هستند:

• آغاز، که در آن متغیرهای مسئله کدبندی می شوند و جمعیت اولیه ایجاد می گردد؛ به طور تصادفی در بین ناحیه ی مطلوب. انها در جهات مختلف می خزند طوری که شعاع نباید بیشتر از R باشد.
• ارزیابی، که در آن تابع هدف برای تمامی مورچه ها محاسبه می شود.
• افزایش دنباله که در آن یک مقدار دنباله برای هر مورچه اضافه می گردد؛ به طور متناسب با تابع هدف محاسبه شده برای آن (که تناسب نامیده می شود).
• مورچه ها در حال ارسال که در آن مورچه ها به دیگر غده های آنها می فرستند، مطابق با دانسیته دنباله و قابلیت مشاهدگی.
• ما اکنون دانسیته ی دنباله را به عنوان فرومون منتشر شده، شرح دادیم. مورچه ها به طور کامل نابینا نیستند و تا حدی بر اساس مشاهده پذیری غده حرکت خواهند کرد. این دو عمل، مراحل درگیر در الگوریتم های PS و TS را یادآوری می کند (تشدید و تنوع) تا از به دام افتادن در ناحیه ی بهینه ی محلی دوری کند.
• تبخیر که در آن دنباله ی منتشر شده توسط هر مورچه بالاخره تبخیر شده و نقطه ی شروع با بهترین یافته ی ترکیب، مطابقت پیدا می کند.