دانلود رایگان کتاب بهینه سازی چند هدفه – Multiobjective Optimization

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

موضوع بحث کتاب بهینه سازی چند هدفه (Muti-objective Optimization)، مسائلی است که دارای دو یا چند معیار بهینگی هستند که غالبا با هم در تعارض می باشند. این گونه مسائل، در شاخه های مختلف علوم پایه، مهندسی و اقتصاد، روز به روز بیشتر مطرح می شوند و از این رو نیاز به روش های مناسب برای حل دقیق و صحیح این مسائل، در حال افزایش است. مشکل اصلی که در برخورد با این گونه مسائل مطرح است، این است که، بر خلاف مسائل بهینه سازی تک هدفه که دارای یک جواب بهینه هستند، در مسائل بهینه سازی چند هدفه، مجموعه ای از جواب ها وجود دارند که هر کدام از دیدگاهی می توانند بهینه باشند. این مجموعه از جواب ها در حوزه بهینه سازی چند هدفه، به جبهه پارتو یا Pareto Front معروف هستند. لذا الگوریتم های خاصی برای برخورد با این گونه مسائل طراحی شده اند که در این کتاب به مفاهیم اساسی این روش ها پرداخته شده است. مطالعه این کتاب برای افرادی که می خواهند از الگوریتم رقابت استعماری در حل مسائل چند هدفه خود استفاده کنند، نیز مفید خواهد بود.
لینک دانلود این کتاب در ادامه قرار داده شده است:

هفتمین کنفرانس بین المللی مهندسی صنایع

دانشكده مهندسی صنايع دانشگاه صنعتی اصفهان با همكاری انجمن مهندسی صنايع ايران، هفتمین کنفرانس بین المللی مهندسی صنایع را در تاریخ ۱۴ و ۱۵ مهرماه ۱۳۸۹ برگزار می‌نماید. بدین وسیله از كلیه پژوهشگران، صاحب نظران، متخصصان و علاقمندان در رشته های مختلف مهندسی صنایع دعوت می‌شود تا مقالات خود حاوی آخرین یافته‌های علمی در زمینه‌های موضوعی كنفرانس را به دبیرخانه كنفرانس ارسال نمایند.
عنوان کنفرانس: هفتمين كنفرانس بين المللي مهندسي صنايع
 
7th International Industrial Engineering Conference
تاريخ برگزاري: 14 مهر 1389 تا 15 مهر 1389
برگزار کننده: انجمن مهندسي صنايع ايران
سایر برگزار کنندگان: دانشكده مهندسي صنايع دانشگاه صنعتي اصفهان
محل برگزاري: اصفهان
تاریخ‌های مهم:
مهلت ارسال اصل مقاله: 1389/2/10
دریافت نسخه نهایی مقالات: 1389/5/20
اعلام نتایج داوری اصل مقاله: 1389/4/20
مهلت ثبت نام: 1389/7/14
محورهاي اصلي كنفرانس
  • برنامه‌ريزي و كنترل توليد و موجودي
  • بهينه سازي و برنامه‌ريزي رياضي
  • توالي عمليات و زمان‌بندي
  • جايابي / طراحي استقرار
  • حمل و نقل و لجستيك
  • داده‌كاوي و كشف دانش (اطلاعات)
  • روش‌هاي تصميم‌گيري
  • روشهاي فرا ابتكاري در مهندسي صنايع
  • سيستم‌هاي ساخت و توليد پيشرفته
  • طراحي و مديريت زنجيره تأمين
  • كاربردهاي مهندسي صنايع در صنعت و خدمات
  • مدل‌سازي و شبيه‌سازي سيستم‌ها
  • مدل‌هاي احتمالي / فازي
  • مديريت كيفيت، مهندسي كيفيت
  • مديريت، برنامه‌ريزي وكنترل پروژه
  • قابليت اطمينان و مديريت نگهداري و تعميرات
  • مهندسي فاكتورهاي انساني
  • هوش مصنوعي و سيستم‌هاي خبره
اطلاعات تماس با دبیرخانه:
تلفن دبيرخانه:
فکس دبيرخانه:
ایمیل: info@iiec2010.com
وب‌سایت: http://www.iiec2010.com/
_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

قدم اول در حل مسئله بهینه سازی مقید با استفاده از الگوریتم رقابت استعماری

این پست در پاسخ سوال یکی از دوستان در مورد نحوه مواجهه با قیود در الگوریتم رقابت استعماری تهیه شده است. مطالعه این پست را به آنهایی که علاقه دارند تا مسائل بهینه سازی مقید خود را با الگوریتم های تکاملی و به طور ویژه با الگوریتم رقابت استعماری حل کنند، توصیه می کنیم. ایده مطرح شده در این پست، کلی بوده و قابل اعمال به همه الگوریتم های تکاملی از جمله الگوریتم های ژنتیک (Genetic Algorithms)، الگوریتم پرندگان یا ازدحام ذرات (Particle Swarm Optimization) و یا کلونی مورچگان (Ant Colony Optimization) می باشد. با ما در ادامه مطلب همراه باشید.

همانگونه که در پست های مختلفی بر روی وبسایت الگوریتم رقابت استعماری و بهینه سازی تکاملی مثلاً در این پست (+) خدمتتان عرض کرده ایم، برای حل مسائل بهینه سازی مقید، اولین قدم، جلوگیری از تولید جوابهای خارج از محدود پذیرفته شده (Feasible Solutions) است. در کدهای الگوریتم رقابت استعماری برای این منظور چه باید کرد؟
اگر شما از کدهای الگوریتم رقابت استعماری استفاده می کنید، سه تابع وجود دارند که باعث ایجاد تغییرات در موقعیت کشورها (تغییر آنها) می شوند. هر یک از این سه بخش باید مورد بررسی قرار گرفته و تغییراتی در آنها ایجاد شود. نکته قابل ذکر این است که اگر قیود ساده و به صورت بازه ثابت برای هر متغیر باشند، نیازی به انجام این تغییرات نیست و نسخه های مختلف کدهای الگوریتم رقابت استعماری بر روی وب بازه اولیه متغیرها را در اول برنامه گرفته و جوابهای نهایی را نیز مطمئناً در این بازه می دهند. پس منظور از قیود، این نوع قیود ساده نیستند. به مثال زیر توجه کنید.

 

فرض کنید می خواهیم در یک مسئله بهینه سازی در حوزه مدیریت مالی، از مجموع یک بودجه برداشتی بهینه داشته باشیم. یک تابع هدف نیز داریم. قیدی داریم که مجموع برداشت ها باید یک (100 درصد) باشد. این قید هم باید در تولید جوابهای اولیه و هم در ایجاد تغییرات آرام (تابع جذب) و هم در تغییرات ناگهانی (تابع انقلاب) لحاظ شود.
در ورژن اولیه کدها که معمولاً استفاده می شود، این سه تابع به ترتیب عبارتند از
  • GenerateNewCountry
  • AssimilateColonies
  • RevolveColonies
در هر سه این توابع باید خطوطی از کد را اضافه کنیم که جمع متغیرهای تولیدی را برابر با یک کند. مثلاً تابع GenerateNewCountry در حالت اولیه به صورت زیر است.
function NewCountry = GenerateNewCountry(NumOfCountries,ProblemParams)
VarMinMatrix = repmat(ProblemParams.VarMin,NumOfCountries,1);
VarMaxMatrix = repmat(ProblemParams.VarMax,NumOfCountries,1);
NewCountry = (VarMaxMatrix – VarMinMatrix) . rand(size(VarMinMatrix)) + VarMinMatrix;
end
با اضافه کردن یک خط می توان مجموع اجزای یک کشور را در مرحله ایجاد برابر با یک کرد. تابع تغییر یافته و خط اضافه شده را در زیر می بینید.
function NewCountry = GenerateNewCountry(NumOfCountries,ProblemParams)
VarMinMatrix = repmat(ProblemParams.VarMin,NumOfCountries,1);
VarMaxMatrix = repmat(ProblemParams.VarMax,NumOfCountries,1);
NewCountry = (VarMaxMatrix – VarMinMatrix) . rand(size(VarMinMatrix)) + VarMinMatrix;
%% Normalizing the sum of population to 1
NewCountry = NewCountry . repmat(sum(NewCountry,2),1,ProblemParams.NPar);
end

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

تغییرات مشابهی در توابع بعدی نیز باید ایجاد شود. دو تابع بعدی را به ترتیب در زیر آورده ایم.

تابع AssimilateColonies در حالت اولیه

function TheEmpire = AssimilateColonies(TheEmpire,AlgorithmParams,ProblemParams)
NumOfColonies = size(TheEmpire.ColoniesPosition,1);
Vector = repmat(TheEmpire.ImperialistPosition,NumOfColonies,1)-TheEmpire.ColoniesPosition;
TheEmpire.ColoniesPosition = TheEmpire.ColoniesPosition + 2 AlgorithmParams.AssimilationCoefficient rand(size(Vector)) . Vector;
MinVarMatrix = repmat(ProblemParams.VarMin,NumOfColonies,1);
MaxVarMatrix = repmat(ProblemParams.VarMax,NumOfColonies,1);
TheEmpire.ColoniesPosition=max(TheEmpire.ColoniesPosition,MinVarMatrix);
TheEmpire.ColoniesPosition=min(TheEmpire.ColoniesPosition,MaxVarMatrix);
end

تابع AssimilateColonies در حالت تغییر یافته

function TheEmpire = AssimilateColonies(TheEmpire,AlgorithmParams,ProblemParams)
NumOfColonies = size(TheEmpire.ColoniesPosition,1);
Vector = repmat(TheEmpire.ImperialistPosition,NumOfColonies,1)-TheEmpire.ColoniesPosition;
TheEmpire.ColoniesPosition = TheEmpire.ColoniesPosition + 2 AlgorithmParams.AssimilationCoefficient rand(size(Vector)) . Vector;
%% Modifying Population according to Conditions
MinVarMatrix = repmat(ProblemParams.VarMin,NumOfColonies,1);
MaxVarMatrix = repmat(ProblemParams.VarMax,NumOfColonies,1);
TheEmpire.ColoniesPosition=max(TheEmpire.ColoniesPosition,MinVarMatrix);
TheEmpire.ColoniesPosition=min(TheEmpire.ColoniesPosition,MaxVarMatrix);
TheEmpire.ColoniesPosition = TheEmpire.ColoniesPosition .      repmat(sum(TheEmpire.ColoniesPosition,2),1,ProblemParams.NPar);
end

تابع RevolveColonies در حالت اولیه

function TheEmpire = RevolveColonies(TheEmpire,AlgorithmParams,ProblemParams)
NumOfRevolvingColonies = round(AlgorithmParams.RevolutionRate numel(TheEmpire.ColoniesCost));
RevolvedPosition = GenerateNewCountry(NumOfRevolvingColonies , ProblemParams);
R = randperm(numel(TheEmpire.ColoniesCost));
R = R(1NumOfRevolvingColonies);
TheEmpire.ColoniesPosition(R,) = RevolvedPosition;
MinVarMatrix = repmat(ProblemParams.VarMin,NumOfColonies,1);
MaxVarMatrix = repmat(ProblemParams.VarMax,NumOfColonies,1);
TheEmpire.ColoniesPosition=max(TheEmpire.ColoniesPosition,MinVarMatrix);
TheEmpire.ColoniesPosition=min(TheEmpire.ColoniesPosition,MaxVarMatrix);
end

تابع RevolveColonies در حالت تغییر یافته

function TheEmpire = RevolveColonies(TheEmpire,AlgorithmParams,ProblemParams)
NumOfRevolvingColonies = round(AlgorithmParams.RevolutionRate numel(TheEmpire.ColoniesCost));
RevolvedPosition = GenerateNewCountry(NumOfRevolvingColonies , ProblemParams);
R = randperm(numel(TheEmpire.ColoniesCost));
R = R(1NumOfRevolvingColonies);
TheEmpire.ColoniesPosition(R,) = RevolvedPosition;
%% Modifying Population according to Conditions
NumOfColonies = size(TheEmpire.ColoniesPosition,1);
MinVarMatrix = repmat(ProblemParams.VarMin,NumOfColonies,1);
MaxVarMatrix = repmat(ProblemParams.VarMax,NumOfColonies,1);
TheEmpire.ColoniesPosition=max(TheEmpire.ColoniesPosition,MinVarMatrix);
TheEmpire.ColoniesPosition=min(TheEmpire.ColoniesPosition,MaxVarMatrix);
TheEmpire.ColoniesPosition = TheEmpire.ColoniesPosition . repmat(sum(TheEmpire.ColoniesPosition,2),1,ProblemParams.NPar);
end

با ایجاد این تغییرات تضمین می شود که جواب بهینه نهایی مسئله مجموع یک خواهد داشت.

در زیر نمودار همگرایی مسئله را می بینیم.

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

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

  1. مسئله من تعداد زیادی قید داره، تا جایی که من کد ها رو بررسی کردم باید اونا رو تو 3 جا اعمال کنیم:      RevolveColonies و GenerateNewCountry و AssimilateColonies. اینا درستن یا جای دیگه ای هم هست؟
  2. بعد از تولید جمعیت اولیه ( یا مراحل بعدی) به صورت اتفاقی، شرایط رو اعمال میکنم و اگر جواب نداد هر مرحله رو از اول تکرار میکنم تا جمعیت ها حتما قیود رو شامل باشن و این کار خیلی سرعت رو پایین میاره آیا راه حلی برای بهبود این وضعیت هست؟

پاسخ ها:

  1. دقیقاً این بخشها هستند که باید تغییر پیدا کنند. تازه اینها بخشهایی هستند در صورت استفاده از “سیاست پیشگیری”، باید تغییر یابند. اگر از سیاست جریمه استفاده شوند، همین ها هم نیازی به تغییر ندارند! در این مورد فرض بر این هست که شما فایل صوتی زیر را مورد استفاده قرار داده اید!
    1. http://www.icasite.info/2010/05/blog-post_1525.html
  2. این بخش نیاز به خلاقیت در هر مسئله دارد. به عنوان یک مثال ساده، مثلاً وقتی قیدها قرار است مجموعشان برابر عدد یک شود، شما می توانید همیشه یکی از متغیرها را برابر یک منهای بقیه تعریف کنید. روش دیگر می تواند، تقسیم همه اعداد به مجموع شان باشد. بسته به شرایط، هر یک از این دو روش می تواند مناسب تر از دیگری باشد. اینکه چه راهی مناسب تر است، نیاز به ایده زنی در آن مسئله دارد. در ضمن اگر دیدید این مسیر سخت می شود، استفاده از متدهای کلی مبتنی بر جریمه پیش روی شماست! در نهایت این را هم در نظر بگیرید که چرخه مورد نظر نباید آنقدر پیچیده و با تغییرات بسیار در جوابها باشد که اطلاعات جواب را از میان ببرد. یعنی فقط به خاطر قیدها آنقدر روی جوابها کار شود که معلوم نشود از کجا آمدند و به کجا رفتند. در این شرایط ممکن است الگوریتم گیج شود. چون کلی انرژی بر روی حرکت در مسیر خاصی گذاشته شده و بعد شما بصورت میانبر آن جواب را وارد حوزه ممکنه جوابها کرده باشید، بدون اینکه الگوریتم بفهمد از چه مسیری به اینجا رسید تا دفعه بعد نیز، حواسش باشد. در حقیقت همان سیستم ماهی و ماهی گیری می شود. باید شما به الگوریتم با قیدهایتان، ماهیگیری یاد دهید.
_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.

صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

انواع مسائل بهینه سازی و تقسیم بندی آنها

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

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

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

\begin{array}{l}  f(x) = {x^2} + \sin (x) \\   x \in [ - 10,10] \\   \end{array}

یک نمونه از یک مسئله چند یعدی (3 بعدی) به صورت زیر می باشد.

\begin{array}{l}  f(x,y,z) = {x^2} + {y^2} + {z^2} + \sin (x) + \sin (y) + \sin (z) \\   x,y,z \in [ - 10,10] \\   \end{array}

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

\begin{array}{l}  f(x,y) = {x^2} + {y^2} + \sin (x) + \sin (y) \\   x,y \in [ - 10,10] \\   \end{array}

یک حالت تغییر پذیر با زمان این تابع به صورت زیر نشان داده می شود.

\begin{array}{l}  f(x,y,t) = {x^2} + {y^2} + \sin (x/t) + \sin (y/t) \\   x,y \in [ - 10,10] \\   \end{array}

جواب هر دو مسئله بهینه سازی فوق نقطه (0,0) است. حتی تابع دوم نیز که متغیر با زمان می باشد برای هر لطحظه از زمان t به جواب (0,0) می رسد. اما این حالت کلی نمی باشد و در حالت کلی جواب بهینه مسئله پارامتر زمان را نیز با خود خواهد داشت.

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

f(x,y) = {x^2} + {y^2} + \sin (x) + \sin (y)
x,y \in [ - 10,10]
{x^2} + {y^2} \le 20
x - y \ge 15

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

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

\begin{array}{l}  {f_1} = 20 + {x^2} + {y^2} - 10*(\cos (2\pi x) + \cos (2\pi y)) \\   x,y \in [ - 10,10] \\   \end{array}

این تابع به تابع راسریجین معروف است و نقطه بهینه این تابع نقطه (0,0) است. شکل زیر این تابع را نشان می دهد.

 

\begin{array}{l}  {f_1} = 20 + {n^2} + {m^2} - 10*(\cos (2\pi n) + \cos (2\pi m)) \\   n,m \in [ - 10, - 9, - 8,.\,.\,.\,,8,9,10] \\   \end{array}

به عنوان مثالی از یک مسئله بهینه سازی گسسته، همان تابع فوق را بصورت گسسته در نظر می گیریم.

نقطه بهینه این تابع نقطه (0,0) است. شکل این تابع در زیر نشان داده شده است.

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

بهینه سازی تک معیاره و چند معیاره
یک مسئله بهینه سازی تک معیاره (Single Objective)، دارای تنها یک تابع هدف می باشد. مثالی از این نوع مسئله بهینه سازی به صورت زیر می باشد.

\begin{array}{l}  {f_1} = 20 + {x^2} + {y^2} - 10*(\cos (2\pi x) + \cos (2\pi y)) \\   x,y \in [ - 10,10] \\   \end{array}

اما در یک مسئله چند معیاره (Multi Objective)، تعداد تابع هدف هایی که بطور همزمان بهینه می شوند بیش از یک تا است. مثال از این نوع مسئله بهینه سازی به صورت زیر می باشد.

\begin{array}{l}  {f_1} = 10 + {x^2} + {y^2} - 10*(\cos (\pi x) + \cos (\pi y)) \\   {f_2} = 20 + {x^3} + {y^3} - 20*(\cos (2\pi x) + \cos (2\pi y)) \\   x,y \in [ - 10,10] \\   \end{array}
این مسئله دارای دو تابع هدف می باشد که باید بطور همزمان بهینه شوند. اگر فرض کنیم که توابع فوق مسائل مینیمم سازی هستند، در این صورت به عنوان مثال جواب ({f_1},{f_2}) = (10,11) در مقابل جواب ({f_1},{f_2}) = (20,22) بهتر بوده و انتخاب مناسب تری می باشد. اما در مقابل آن جواب (یعنی ({f_1},{f_2}) = (10,11))، جواب ({f_1},{f_2}) = (9,12) نه بهتر است نه بدتر. در حقیقت از دید {f_2} جواب اول بهتر است و از دید {f_1} جواب دوم. مجموعه جوابهایی که هیچ برتری نسبت به هم ندارند تشکیل یک منحنی را در صفحه می دهند که به نام منحنی پرتو (Pareto) شناخته می شود. شکل زیر یک منحنی پرتو مربوط به یک مسئله بهینه سازی نوعی را نشان می دهد.

 

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

حل مسائل بهینه سازی چند هدفه و رسیدن به منحنی پرتو، به تنهایی مبحث مستقل و مهمی از حوزه بهینه سازی می باشد. نسخه های ویژه الگوریتم رقابت استعماری برای حل مسائل بهینه سازی چند هدفه پس از انتشار بر روی سایت قرار خواهد گرفت.

——————————————–
مراجع: در تهیه این متن از بخش هایی از سمینار کارشناسی ارشد جناب آقای سید مصطفی کلامی هریس استفاده شده است.

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

نحوه مواجهه با قید ها در بهینه سازی مقید

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

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

لینک های دانلود

نکته: در صورت استفاده از سرور شماره چهار جهت دانلود، باید از طریق اکانت گوگل (یا همان جیمیل) خود پس از کلیک بر روی لینک ها وارد شوید.

پیاده سازی متنی فایل صوتی

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

با سلام
در مورد مدیریت قیدها در الگوریتم های تکاملی از جمله الگوریتیم ژنتیک، الگوریتم پرندگان، زنبور عسل و الگوریتم رقابت استعماری و کلاً مسأله ای که مطرح است این است که روش هایی که موجود هستند و ما از آن ها استفاده می کنیم مستقل از نوع الگوریتم هستند. یعنی این، این طور نیستند که بگوییم روش هندل کردن قید در فلان جا. معمولاً روشی مدیریت قیود (Constraint Handling) که برای یک الگوریتم استفاده می شود برای یک الگوریتم دیگر هم قابل استفاده است. ما خود را محدود به هیچ الگوریتمی نمی کنیم و کلاً بازی کردن با قیدها مبحث جداگانه و تخصص جداگانه ای از کارکردن با خود فقط الگوریتم است.

ساده ترین روشی که برای مدیریت قیود استفاده می شود این است که در روش های تکاملی ما یک تابع هزینه ای داریم که این تابع هزینه ها را با یک برنامه جداگانه می خواهیم مینیمم یا ماکس آن را پیدا کنیم. که آن برنامه جداگانه می تواند برنامه الگوریتم ژنتیک، پرندگان باشد و غیره.
اولاً باید برنامه ها را از همان ابتدا برای این که بتوانیم جواب خوب بگیریم ماژولار بنویسیم. (یعنی تابع هزینه را از خود برنامه جدا کنیم). بعضی وقت ها دیده می شود که توی بعضی برنامه ها، افراد کل مسأله خود را در یک برنامه می نویسند.

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

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

حالا برویم سراغ های پیشگیری. روش های پیشگیری می گویند که اگر آن چیزی که اسمش را می گذاریم مجرم، در جامعه سعی کنیم نگذاریم متولد بشود. اگر مجرم متولد شد پانیش (تنبیه) کنیم. مثلاً یک قانون می تواند این باشد که هر کسی که پایش را فراتر از حدودی که تعیین شده گذاشت، اعدامش کنیم. این ساده ترین و کم پیچیده ترین قانونی است که می شود تصویب کرد. چه کار می کنیم؟ در الگوریتم ژنتیک می آییم پنالتی می گذاریم. مثلاً ما می دانیم که هزینه هایمان چه هستند.

به عبارت دیگر، خوب ما می خوایم مسأله مینیمم سازی حل کنیم یعنی هر چه کمتر باشد بهتر است ما می دانیم که هزینه هایمان بین منفی 10 تا 100 است یهو می آییم به آن جواب هایی که خیلی از قیود ما بیرون رفتند چه کار می کنیم؟ یهو یه پنالتی می دیم. مثلاً صد میلیون. یعنی چی؟ یعنی این می رود تو ته لیست جمعیت قرار می گیرد. خوب اعدام می شود یعنی می رود ته جمعیت ته لیست جمعیت و از جمعیت بیرون انداخته می شود. یعنی ما کافیه که در تابع هزینه مون که گفتیم به صورت جداگانه ما این رو نوشتیم یک تابع هزینه داریم f(x). داخل اون می نویسم f،x ؟؟ مثلاً اگر gx که هزینه ما هست کوچکتر از صفر شد همیشه می شود الگویش را می شود به این صورت نوشت. حالا بزرگ تر شد هر چی شد یعنی اگر عدول کرد، هزینه اش را بالا می گذاریم. مثلاً صد میلیارد. خوب این هم پس، آن یکی روش. روش اول که پیشگیری بود. روش درمان اولیه و سطحی که به ذهن می رسد همین است. این هم اگر جواب داد، ساده ترین کاری است که می شود انجام داد یعنی ما اگر بتوانیم با این روش کار را جلو ببریم می توانیم تا حدی خودمان را از پیچیدگی روشهای دیگر که در ادامه می گوییم رها کنیم. خوب ادامه را در بخش دوم ببینید.

خوب حالا ببینیم که اگر آن روش، بدیش چیه؟ آن روش بدیش اینه که اگر، شما جامعه ای را در نظر بگیرید که ما افراد به خاطر عبور از خط قرمز، به خاطر کشتن آدم، به خاطر توهین به فلانی به خاطر اعتراض به هر دلیلی یه مجازات اعدام بگذاریم جلویش یهو می بینیم که نصف آن جامعه مجرم هستند؛ یعنی حتی بیشتر از نصف یعنی وقتی ما با قیود پیچیده مواجه هستیم این روش جواب نمی دهد چون با عث می شود که اگر اعضای جمعیت ما مثلاً اگر صدتایی است با آن تعریفی که ما از جرم انجام داده ایم یهو می بینیم که 90 درصد از جامعه ما مجرم هستند و باید پانیش (نتبیه) بشوند و باید بروند ته لیست. در حقیقت، آن موقع ته لیستی اصلاً نیست که جمعیت برود ته لیست. ته لیست موقعی معنی دارد که ما صدتا عوض جمعیت داریم و پنج تاشون، دوتاشون، قیود را زیر پا می گذارند و ما آنها را می فرستیم ته لیست تا تنبیه بشوند. منتها وقتی که از صدتا جمعیت ما، در قیود پیچیده واقعاً مسائل همین گونه هستند یعنی آن قدر فضای در دسترس (Feasible Space) یعنی ناحیه ای که فیزبل (در دسترس) هست، جواب ها باید توش باشند؛ آن قدر نسبت به فضای کل جستجو کوچک هست، آن قدر قیود ما برای در حقیقت تعریف جرم بسته هست که کل جامعه خیلی وقت ها، خیلی وقت ها می شود بله، صد رصد حتی مجرم هستند . خوب ما می آییم فرض کنید روش در حقیقت مجازات که همشون را کاست (هزینه) صد میلیارد بدهیم در نظر می گیرم. خوب ما در نظر بگیرید جمعیتی را که صد تا عنصر توی جمعیتش وجود دارد ما به همشون کاست صد میلیارد دادیم؛ خوب یه لیستی داره یک سری افرادی در آن هستند همه اعدام. هیچ فرقی بین جرم پایین و کوچک و بالا وجود ندارد. مجازات، کل فلسفه اش اینه که ما بخواهیم جمعیت را اصلاح کنیم. ما که اینجا نمی خواهیم از جمعیت انتقام بگیریم؟!! هدف اینه که می خواهیم برسیم به یک جواب خوب. برسیم به یک جمعیت بهبود یافته. برسیم به جواب مسألمون. جواب هایی که افرادی که هستند که در قیود ما صدق می کنند. پس خلاصه بخواهیم بگوییم در مواردی که قیود، فضایی را ایجاد می کنند که فیزبل سولوشن (ناحیه در دسترس) ما خیلی کوچکتر است از آن فضایی که ما جستجو را از آن شروع کردیم و هیچ سنسی (احساسی) از فضای اصلی نداریم، در چنین مواردی با احتمال کمی پاپیولیشن ها می افتند داخل آن قیود.

خوب در مواردی که ناحیه در دسترس ما خیلی نسبت به فضای جستجوی اصلی که ما جستجو را باهاش شروع کردیم، کوچک هست، روش تنبیه مساوی و بزرگ برای کل جمعیت روش مناسبی نیست. خوب این را می توانیم خیلی ساده تست کنیم. می آییم چه کار می کنیم؟ می آییم پاپیولیشن (جمعیت) مثلاً هزارتایی را در نظر می گیرم. بعد این ها را به صورت تصادفی تولید می کنیم در آن فضای اولیه حدس. خوب این ها را پخش می کنیم بعد قیود را در نظر می گیریم اگر دیدیم مثلاً از این هزارتا فقط20 تا 50 تا فوقش 100 تا یعنی ده درصد قیود را رد کردند و بقیه در فضای اصلی هستند، همون تنبیه ساده کافیه. منتها یهو دیدیم از آن هزارتایی که ما تولید کردیم دو تا فقط هست یا حتی یک دانه و یا حتی اصلاً نیست در قیود ما صدق کند این روش دیگه جواب نمی دهد می پره این ور و آن ور.

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

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

روش سوم این است که ما بیاییم متناسب با عدول از قیود، پانیشمنت در نظر بگیریم. این به چه صورت است؟ می آییم می گویم مثلاً اگر قرار بود که x2 +x1 کوچکتر از 10 باشد و حالا، بزرگتر از 10 شده، نیائیم هر کروموزمی که x1+x2 برای آن؛ بزرگتر از 10 هست، پانیش کنیم. بیاییم چه کار کنیم؟ بیائیم میزان تنبیه رو برابر با میزان عدول در نظر بگیریم.

مثلاً به چه میزان از x1+x2 که باید 10 می شد بزرگتر است. اگه 11 هست یک واحد پانیش کنیم اگر 15 هست 5 واحد پانیش کنیم اگه 20 هست 10 واحد پانیش کنیم . این یعنی به اصطلاح متناسب با آن میزان عدول از قیود آن ها را پانیش کنیم. این یکی از روشهاست. پس میزان پانیش منت مساوی است با فاصله ای که از قیود می گیرند. مثلاً می توانیم، مثلاً اگر 5 تا قید داریم می گوییم مجموع فواصل از قیود را کمینه کنید.

یک روش هم این است که در کنار این که این ها را در نظر بگیریم تعداد عدول از قیود را هم در نظر می گیریم. معمولاً بعضی روش ها مثلاً اگه 7 یا 8 تا قید داریم می گوییم نه تنها میزان عدولشان بلکه تعداد عدولشان را هم در نظر بگیر. این چیزهایی که گفته می شود این جا، این جا روش استاندارد و کلاسیکی وجود ندارد گفته بشود بله ، این روش کار ماست. نه! این ها آن قدر باید باهاشون بازی بشود تا مناسب ترین روش اصلاح برای آن مسأله به دست بیاید. یعنی این طور نیست که ما قانونی را برای یک کشور تصویب کنیم و همان قانون برای کشور همسایه بتواند آن کشور را اصلاح کند. منتها خوب می شود قانون هایی را بهشون رسید که در میانگین، بهتر از قوانین دیگر جواب می دهند. منتها باید توجه کرد که این یک اکسیر یا کیور آل (cure-all) برای تمام مسائل نیست.

خوب پس چه کار می کنیم؟ یه پنالتی فاکتور در نظر می گیرم. پنالت فاکتور را همیشه می توان با میزان هزینه آن کروموزم جمع کرد یا همیشه درش ضرب کرد. مثلاً می گوییم که کاست (هزینه) هر کروموزم برابر است با کاست اصلیش یعنی میزان تابع هزینه آن به اضافه مثلاً صد برابر، ده برابر یا هر چیزی از عدول از هزینه.

فقط یک مسأله را در نظر داشته باشید که باید خیلی حرفه ای با این مسأله برخورد شود. بعضی وقت ها، مثلاً پنالتی ها به گونه ای هستند که اول کار، خوب جواب می دهند، وسط ها مثلاً یهو می بینی که مسأله، بهینه سازی می شود؛ منتها در نهایت جواب می دهد که باز خارج از قیود ما هست. ریشه کار به چی بر می گردد؟ ریشه کار به این برمی گردد که شما اگر با موبایل داخل ماشین نشسته و صحبت کنید، جریمه اش مثلاً 10 هزار تومان است. منتها خیلی از افراد یک معامله مثلاً یک میلیونی را با همان مکالمه 5 دقیقه ای که اگه بگیرنش 10 هزار تومان جریمه اش باشد؛ انجام می دهند. یعنی پاپیولیشن ها (اعضای جمعیت) ما هم بعضی وقت ها می روند، قیدها را زیر پا می گذارند. منتها از این طرف، توی تابع هزینه یه جاهایی را پیدا می کنند که هزینه آن قدر کم می شود که شما اگر هزینه تمام قیود را جمع کنید و در نهایت باز جبران آن عدول از قیود نمی شود. یعنی در حقیقت می شود گفت پانیش منت (تنبیه) ما خیلی شُل هست. یعنی جامعه را خیلی شُل گرفتیم. این به این معنی نیست که بیاییم پانیش منت را بگیریم هر چی شد تابع به اضافه صد برابر عدول از قیود. نه! پانیش منت را باید در طی مسأله باید کم کنیم، زیاد کنیم، این ها چیزهایی که باید باهاشون مدتی بازی بشود که دستتون کاملاً بیاد.

کلاً paper های کانسرنت هندلنگ (مدیریت قیود) خیلی زیاد هستند. در مورد این ها می توانیم مجزا مطالعه کنیم. منتها این روش هایی که گفتم، روش های عام این قضیه هستند و می توانیم با مقداری بازی کردن باهاشون، کار کنید.

حالا باز همانگونه که عرض کردم خدمتتون، هیچ تفاوتی بین الگوریتم ژنتیک و دیگر الگوریتم ها نیست. مثلاً خیلی وقت ها من ایمیل دریافت می کنم که من الگوریتم رقابت استعماری را که الگوریتم جدید و کارایی در حوزه بهینه سازی هست را دارم استفاده می کنم. در مورد این الگوریتم، قیود را چه کار کنیم؟ جوابشون را من معمولاً این طور می دهم که همان کاری را که با ژنتیک می کنیم با همین هم بکنید. منتها اگر ژنتیک را بلد نیستید این یک بحث مجزاست. یعنی همان قیود را که در مورد ژنتیک کار می کنید، همان کار تکرار می شود برای الگوریتم پرندگان، الگوریتم مورچگان، برای الگوریتم رقابت استعماری. همشون تکراری، همین موارد هستند. امیدوارم این توضیحات تا حدی توانسته باشد بعضی از سؤالات را جواب بدهد، بقیه اش هم که دیگه تجربه شخصی است. باید با برنامه نویسی و … این ها به دست بیاید. موفق باشید و خدا نگهدار.

در ضمن نگاهی به مقالات منتشر شده در مورد الگوریتم رقابت استعماری در بخش مقالات و پایان نامه ها در سایت داشته باشید. مقالات خوبی در زمینه مدیریت قیود را خواهید دید.

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