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

/2 دیدگاه /در , , , /توسط

این پست در پاسخ سوال یکی از دوستان در مورد نحوه مواجهه با قیود در الگوریتم رقابت استعماری تهیه شده است. مطالعه این پست را به آنهایی که علاقه دارند تا مسائل بهینه سازی مقید خود را با الگوریتم های تکاملی و به طور ویژه با الگوریتم رقابت استعماری حل کنند، توصیه می کنیم. ایده مطرح شده در این پست، کلی بوده و قابل اعمال به همه الگوریتم های تکاملی از جمله الگوریتم های ژنتیک (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. این بخش نیاز به خلاقیت در هر مسئله دارد. به عنوان یک مثال ساده، مثلاً وقتی قیدها قرار است مجموعشان برابر عدد یک شود، شما می توانید همیشه یکی از متغیرها را برابر یک منهای بقیه تعریف کنید. روش دیگر می تواند، تقسیم همه اعداد به مجموع شان باشد. بسته به شرایط، هر یک از این دو روش می تواند مناسب تر از دیگری باشد. اینکه چه راهی مناسب تر است، نیاز به ایده زنی در آن مسئله دارد. در ضمن اگر دیدید این مسیر سخت می شود، استفاده از متدهای کلی مبتنی بر جریمه پیش روی شماست! در نهایت این را هم در نظر بگیرید که چرخه مورد نظر نباید آنقدر پیچیده و با تغییرات بسیار در جوابها باشد که اطلاعات جواب را از میان ببرد. یعنی فقط به خاطر قیدها آنقدر روی جوابها کار شود که معلوم نشود از کجا آمدند و به کجا رفتند. در این شرایط ممکن است الگوریتم گیج شود. چون کلی انرژی بر روی حرکت در مسیر خاصی گذاشته شده و بعد شما بصورت میانبر آن جواب را وارد حوزه ممکنه جوابها کرده باشید، بدون اینکه الگوریتم بفهمد از چه مسیری به اینجا رسید تا دفعه بعد نیز، حواسش باشد. در حقیقت همان سیستم ماهی و ماهی گیری می شود. باید شما به الگوریتم با قیدهایتان، ماهیگیری یاد دهید.
_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.

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

2 پاسخ
  1. Anonymous
    Anonymous گفته:

    با سلام و عرض خسته نباشید خدمت شما دستتون درد نکنه ولی اگه بخواهیم یک محدودیت غیر خطی از نوع نامساوی اضافه کنیم چکار باید بکنیم؟

    پاسخ

دیدگاه خود را ثبت کنید

تمایل دارید در گفتگوها شرکت کنید؟
در گفتگو ها شرکت کنید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *