الگوریتم CMAES در متلب – الگوریتم CMAES (استراتژی تکاملی انطباق ماتریس کوواریانس) در متلب

سورس کد الگوریتم CMAES در متلب عنوان موضوعی است که در این پست به آن پرداخته می‌شود. الگوریتم CMA-ES از جمله الگوریتم‌های تکاملی شناخته شده‌‌ی بهینه‌سازی است که از یک توزیع نرمال، نمونه‌گیری کرده و جمعیت جدید را به وجود می‌آورد. این الگوریتم تکاملی یک ماتریس کواریانس و یک بردار میانگین را از جمعیت تخمین می‌زند. قوانین مختلف به روز‌رسانی، ماتریس کواریانس تطبیق یافته‌ای را در هر نسل ایجاد می‌کند که در کیفیت جمعیت جدید و در نتیجه هدایت تکامل نقش مهمی دارد.

الگوریتم CMAES

این الگوریتم مخفف Covariance Matrix Adaptation Evolution Strategy به معنای استراتژی تکاملی انطباق ماتریس کوواریانس می‌باشد. دو اصل اصلی برای سازگاری پارامترهای توزیع جستجو در الگوریتم CMA-ES مورد استفاده قرار می‌گیرند.

ابتدا، یک اصل حداکثر احتمال maximum-likelihood، برای افزایش احتمال موفقیت راه‌حل‌های کاندید شده و مراحل جستجو در نظر گرفته می‌شود. متوسط توزیع به روز می‌شود به طوری که احتمال موفقیت پیشین موفق به راه حل‌های حداکثر می‌شود. ماتریس کوواریانس توزیع (به طور تدریجی) به روز می‌شود به طوری که احتمال مراحل پیشین موفق جستجو افزایش می‌یابد.

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

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

مسیر دیگر مورد استفاده برای کنترل اضافی اندازه گام است. هدف این کنترل گام به گام، ایجاد حرکات متوالی از توزیع به طور متعادل در انتظار است. کنترل گام اندازه گیری به طور موثر مانع از همگرایی زودرس می‌شود، اما همگام سازی سریع را به بهترین وجه امکان می‌دهد.

شبه کد الگوریتم CMAES

در زیر، بیشترین استفاده الگوریتم μ / μw، λ -CMA-ES مشخص شده است، که در هر گام تکرار ترکیبی وزنی از μ بهترین از λ راه حل‌های نامزد جدید برای به روز رسانی پارامترهای توزیع استفاده می‌شود. حلقه اصلی شامل سه بخش اصلی است:

۱) نمونه برداری از راه حل‌های جدید؛

۲) ترتیب مجدد راه حل‌های نمونه بر اساس تناسب آن؛

۳) به روز رسانی متغیرهای حالت داخلی بر اساس نمونه‌های مرتب شده.

یک pseudocode از الگوریتم به شرح زیر است.

سورس کد الگوریتم CMAES در متلب

سورس کد الگوریتم CMAES شامل توابعی است که تابع CMAES در واقع کد اصلی برنامه می‌باشد و بقیه فراخوانی‌ها از آن‌جا انجام می‌شود. همچنین این برنامه با ۷ تابع تست ارائه شده است. توابع تست برای ارزیابی الگوریتم های بهینه سازی بکار می‌روند که در این سایت برای توضیحات بیشتر در مورد توابع تست الگوریتم های بهینه سازی مقاله ای آماده کردیم. توابع تست این پروژه عبارتند از :

• تابع  SPHERE
• تابع ACKLEY
• تابع SUM SQUARES
•  تابع ROSENBROCK
• تابع SUM OF DIFFERENT POWERS
• تابع ZAKHAROV
• تابع Rastrigin

توابع زیادی برای تست عملکرد الگوریتم های بهینه سازی وجود دارد که در اینجا ما به این ۷ تابع اکتفا کرده‌ایم. همچنین لازم به ذکر است که برای اجرای الگوریتم بهینه سازی روی مسئله مورد نظر تابع هزینه یا Cost Function آن تغییر خواهد کرد و بقیه الگوریتم دست نخورده باقی می‌ماند. بنابراین برای اجرای الگوریتم CMAES در متلب برای بهینه سازی مسئله خودتان تابع هزینه خود را بر اساس پارامترهای مسئله خود تعریف کنید.

قسمتی از سورس کد الگوریتم CMAES در متلب

clc;
clear;
close all;

%% Problem Settings

 CostFunction=@(x) Sphere(x);        % Cost Function
% CostFunction=@(x) Sum_Squares(x);        % Cost Function
% CostFunction=@(x) Sum_Of_Different(x);        % Cost Function
% CostFunction=@(x) Ackley(x);        % Cost Function
%CostFunction=@(x) Rosenbrock(x);        % Cost Function
% CostFunction=@(x) Zakharov(x);        % Cost Function
% CostFunction=@(x) Rastrigin(x);

nVar=10;                % Number of Unknown (Decision) Variables

VarSize=[1 nVar];       % Decision Variables Matrix Size

VarMin=-10;             % Lower Bound of Decision Variables
VarMax= 10;             % Upper Bound of Decision Variables

%% CMA-ES Settings

% Maximum Number of Iterations
MaxIt=300;

% Population Size (and Number of Offsprings)
lambda=(4+round(3*log(nVar)))*10;

% Number of Parents
mu=round(lambda/2);

% Parent Weights
w=log(mu+0.5)-log(1:mu);
w=w/sum(w);

% Number of Effective Solutions
mu_eff=1/sum(w.^2);

% Step Size Control Parameters (c_sigma and d_sigma);
sigma0=0.3*(VarMax-VarMin);
cs=(mu_eff+2)/(nVar+mu_eff+5);
ds=1+cs+2*max(sqrt((mu_eff-1)/(nVar+1))-1,0);
ENN=sqrt(nVar)*(1-1/(4*nVar)+1/(21*nVar^2));

% Covariance Update Parameters
cc=(4+mu_eff/nVar)/(4+nVar+2*mu_eff/nVar);
c1=2/((nVar+1.3)^2+mu_eff);
alpha_mu=2;
cmu=min(1-c1,alpha_mu*(mu_eff-2+1/mu_eff)/((nVar+2)^2+alpha_mu*mu_eff/2));
hth=(1.4+2/(nVar+1))*ENN;

%% Initialization

ps=cell(MaxIt,1);
pc=cell(MaxIt,1);
C=cell(MaxIt,1);
sigma=cell(MaxIt,1);

ps{1}=zeros(VarSize);
pc{1}=zeros(VarSize);
C{1}=eye(nVar);
sigma{1}=sigma0;

empty_individual.Position=[];
empty_individual.Step=[];
empty_individual.Cost=[];

M=repmat(empty_individual,MaxIt,1);
M(1).Position=unifrnd(VarMin,VarMax,VarSize);
M(1).Step=zeros(VarSize);
M(1).Cost=CostFunction(M(1).Position);

BestSol=M(1);

BestCost=zeros(MaxIt,1);

%% CMA-ES Main Loop

for g=1:MaxIt
    
    % Generate Samples
    pop=repmat(empty_individual,lambda,1);
    for i=1:lambda
        pop(i).Step=mvnrnd(zeros(VarSize),C{g});
        pop(i).Position=M(g).Position+sigma{g}*pop(i).Step;
        pop(i).Cost=CostFunction(pop(i).Position);
        
        % Update Best Solution Ever Found
        if pop(i).Cost<BestSol.Cost
            BestSol=pop(i);
        end

برای دانلود سورس کامل محصول را خریداری فرمایید.

تصویر خروجی محصول در سورس کد الگوریتم CMAES در متلب

درباره سورس کد الگوریتم CMAES در متلب

سورس کد الگوریتم CMAES در متلب در محیط Matlab 2017b نوشته و اجرا شده است. این سورس کد توسط تیم پشتیبانی پی استور تست و اجرا شده است. کیفیت اثر توسط پی استور تضمین می‌شود و دارای نشان تضمین کیفیت پی استور می‌باشد. برای دانلود اثر آن را خریداری فرمایید به محض خرید لینک دانلود در دسترس خواهد بود.