پیاده سازی الگوریتم ژنتیک در چندی سازی در متلب

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

الگوریتم را در چند فاز پیاده سازی می کنیم

فاز یک: مقداردهی اولیه (Initialize)

در ابتدا باید تعداد جمعیت اولیه(nPop)، بیشترین تعداد تکرار(maxiter)، اندازه بلوک (bs)و کتاب کد(cbs) را مشخص کنیم بنابراین این مقادیر را به عنوان ورودی برنامه دریافت می کنیم

X=inputdlg({'Population','Iteration','Block Size','Codebook Size'}, 'Input', [1 15;1 15;1 15;1 15]);

nPop=str2double(X{1});

nPop=str2double(X{1}); % Number of Fireflies (Swarm Size)
)

maxiter=str2double(X{2}); % Maximum Number of Iterations

bs=str2double(X{3}); % Block Size

cbs=str2double(X{4}); % Codebook Size

و آرایه data را به صورت زیر تعریف می کنیم که دارای دو ستون باشد که دارای لیبلهای Best Fitness و PSNR می باشد.

data={'Best Fitness','PSNR'}; %Row cell array (for column labels)

حال عکس مورد نظر را می خوانیم و آن را خاکستری می کنیم

A = imread('Baboon.jpg'); % Read training image

A = rgb2gray(A); % convert into gray

در واقع عکس به صورت یک آرایه در A ذخیره شده است بنابراین تعداد ردیف ها را با دستور زیر در متغییر h و تعداد ستون ها در w ذخیره می کنیم

[h,w] = size(A);

سپس تعداد بلوک ها را مشخص می کنیم

nb=(h/bs)*(w/bs);

فاز دوم : مقداردهی پارامترها(Parameters setting)

در این مرحله چندین پارامتر را به شرح زیر مقداردهی می کنیم

pc=0.9; % Crossover percentage 0≤ pc ≤1

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

ncross=round(nPop*pc/2) *2; % Number of Offsprings(Parents)

pm=0.2; % Mutation percentage 0 ≤ pm ≤ 1

نرخ تاثیر جهش

pm یک مقدار حتمی می باشد که به کمک آن تعداد کروموزوم هایی را که باید جهش داشته باشند را مشخص می کنیم pm را در تعداد جمعیت کل ضرب می کنیم و سپس آن را گرد می کنیم اگر pm=1 باشد بدین معنی است که همه مولفه ها را به صورت تصادفی تعویض کن و اگر pm=0باشد یعنی جهش را انجام نگیرد.

nmut=round(nPop*pm); % Number of mutance

e = .01;

dpr = 10000;

فاز سوم : الگوریتم مقداردهی اولیه جمعیت

نوع تمام مقادیر آرایه A را به نوع double تغییر می دهیم

I=double(A);

با دستور زیر بلوک بندی انجام می دهیم و هر بلوک را در یک ستون قرار می دهیم و در آرایه pool می گذاریم

pool=im2col(I,[bs bs],'distinct');

تعداد سطرهای آرایه pool را در متغییر m و تعداد ستون های آن را در متغییر n قرار می دهد

[m,n]=size(pool);

حال یک ساختار با نام emp با دو متغییر var و fit تعریف می کنیم متغییر fit را با مقدار بینهایت مقداردهی اولیه می کنیم

emp.var=[];

emp.fit=inf;

به منظور ساخت جمعیت باید تابع emp به تعداد جمعیت در یک ستون تکرار گردد

pop=repmat(emp,nPop,1);

حال باید pop را مقداردهی کنیم و بدین منظور حلقه for را به تعداد جمعیت تکرار می کنیم و در هر تکرار چیدمان رندم از n ایجاد می کنیم و سپس تمام سطرهای آرایه pool را از ستون اول تا ستون cbs را متغییر var قرار می دهیم سپس آن را توسط تابع Fitness ارزیابی می کنیم و مقدار آن را در متغییر fit می گذاریم

for i=1:nPop

order=randperm(n);

pop(i).var=pool(:,order(1:cbs));

pop(i).fit =Fitness(pool,pop(i).var);

end

حال جمعیت ایجاد شده را مرتب می کنیم

% Sort Population

pop=SortPopulation(pop);

بهترین عضو را که اولین عضو می باشد را در متغییر BestSol قرار می دهیم

% Store Best Solution

BestSol=pop(1);

حال یک آرایه تعریف می کنیم BsetSol هر بار تکرار را در خود نگهداری کند

% Vector to Hold Best fit Values

BEST=zeros(maxiter,1);

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

%% main loop algorithm

It=1;

while It<(maxiter+1)

% crossover

به منظور ساخت جمعیت ترکیب شده باید تابع emp به تعداد ncross در یک ستون تکرار گردد

crosspop=repmat(emp,ncross,1);

سپس این آرایه را به همراه آرایه جمعیت، pool ، تعداد کتاب کد و تعداد کروموزوم هایی که عملیات ترکیب روی آنها انجام می شود را به تابع crossover ارسال می کنیم

crosspop=crossover(crosspop,pop,pool,cbs,ncross);

% mutation

به منظور ساخت جمعیت جهت جهش باید تابع emp به تعداد nmut در یک ستون تکرار گردد

mutpop=repmat(emp,nmut,1);

سپس این آرایه را به همراه آرایه جمعیت، pool ، تعداد کتاب کد و تعداد کروموزوم هایی که عملیات جهش روی آنها انجام می شود را به تابع mutation ارسال می کنیم

mutpop=mutation(mutpop,pop,pool,cbs,nmut,nPop);

% Merge Population

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

pop=[pop

crosspop

mutpop];

%roulette wheel

دستورات زیر احتمال هر کروموزوم و سپس جمع احتمال ها از اول تا هر کروموزوم را محاسبه می کنند

f=[pop.fit];

f=max(f)-f+eps;

f=f./sum(f);

f=cumsum(f);

حال در حلقه زیر یک عدد به صورت رندم بین 0 تا 1 انتخاب می شود و اولین f را که شرط زیر برقرار می گردد را انتخاب کرده و سپس عنصر آن را جایگزین می کند

for i=1:nPop

i1=find(rand<=f,1,'first');

pop(i)=pop(i1);

end

% Sort Population

جمعیت pop را به تابع SortPopulation پاس داده تا آن را مرتب نماید

pop=SortPopulation(pop);

% Update Best Solution

در نهایت بهترین کروموزم که اولین آن می باشد را انتخاب کرده و در BestSol قرار می دهد

BestSol=pop(1);

if It == maxiter

break;

else

It=It+1;

end

تابع Fitness

این تابع دو آرایه pool و pop(i).var دریافت کرده و در متغیرهای x و y قرار می دهد و سپس تعداد سطرهای تابع pool را در متغییر M و تعداد ستون های آن را در متغییر N قرار می دهد سپس این دو آرایه را به تابع disteu ارسال کرده و این تابع فاصله اقلیدوسی بین آنها را محاسبه کرده و در متغییر d قرار می دهد

function F = Fitness( x,y )

[M, N] = size(x);

d = disteu(x, y);

سپس هر عنصر را به توان 2 رسانده

تابع disteu

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

function d = disteu(x, y)

% DISTEU Pairwise Euclidean distances between columns of two matrices

% Input:

% x, y: Two matrices whose each column is an a vector data.

% Output:

% d: Element d(i,j) will be the Euclidean distance between two

% column vectors X(:,i) and Y(:,j)

% Note:

% The Euclidean distance D between two vectors X and Y is:

% D = sum((x-y).^2).^0.5

[M, N] = size(x);

[M2, P] = size(y);

if (M ~= M2)

error('Matrix dimensions do not match.')

end

d = zeros(N, P);

if (N < P)

copies = zeros(1,P);

for n = 1:N

d(n,:) = sum((x(:, n+copies) - y) .^2, 1);

end

else

copies = zeros(1,N);

for p = 1:P

d(:,p) = sum((x - y(:, p+copies)) .^2, 1);

end

تابع SortPopulation

این تابع عملیات مرتب سازی کروموزوم ها را انجام می دهد

function [pop Costs]=SortPopulation(pop)

Costs=[pop.fit];

[Costs SortOrder]=sort(Costs,'descend');

pop=pop(SortOrder);

end

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

%% VQ Encoding

I=double(A);

pool=im2col(I,[bs bs],'distinct');

[m,n]=size(I);

index=zeros(m/bs,n/bs);

for i = 1:numel(index)

temp=repmat(pool(:,i),1,cbs);

[val,ind]=min(sum((temp-BestSol.var).^2));

index(i)=ind;

end

%% VQ Decoding

pool=BestSol.var(:,index(:));

B=uint8(col2im(pool,[bs bs],[h,w],'distinct'));

جمعیت	تکرار	بلوک	کتاب کد	BestSol.fit	PSNR	شماره عکس
300	20	4	30	e^-095.621566281711677	20.253630383798340	1
700	20	4	30	e-096.824565851631752	20.677691126446046	2
1500	20	4	30	e-096.135099079110868	20.485027793347335	3
5000	20	4	30	e-098.499121958083770	21.223360355318760	4
10000	20	4	30	e-097.471352062573485	20.968938692219155	5
300	40	4	30	e-092.660062663269436	19.274208665165270	6
300	60	4	30	e-093.640534994617034	19.657035261529730	7
300	80	4	30	e-092.590034568803999	19.227299420723376	8
700	40	4	30	e-094.112299117605227	19.712780392131940	9
700	60	4	30	e-093.496280994963774	19.443884613396545	10
700	80	4	30	e-094.716882058054114	19.919135288740660	11
1500	40	4	30	e-095.123564758476154	19.973204641932764	12
1500	60	4	30	e-095.303262018582781	20.328925380529345	13
1500	80	4	30	e-093.720157552976171	19.738250231810788	14
10000	40	4	30	e-096.324404055253341	20.630365676986580	15
10000	60	4	30	e-095.073431341348113	20.202805235905256	16
10000	80	4	30	e-094.169634121448476	19.802478345782010	17
300	20	16	30	e-111.095891849736290	18.254831715897530	18
700	20	16	30	e-111.040308130731348	18.138778552887200	19
1500	20	16	30	e-111.072794272258685	18.222451840595410	20
10000	20	16	30	e-111.125354901186219	18.305255723302132	21
300	20	4	40	e-096.781422905094772	20.725927258249676	22
700	20	4	40	e-097.427667661211070	21.034394700434460	23
1500	20	4	40	e-097.504545788416165	21.114540888457700	24
10000	20	4	40	e-097.986502067665150	21.060572310664128	25
300	20	4	50	e-098.496846154057512	21.263864074377356	26
700	20	4	50	e-098.712610133475753	21.382107685804957	27
1500	20	4	50	e-098.835327383145902	21.295408225168010	28
10000	20	4	50	e-099.020574423322650	21.390521871818542	29
300	20	4	60	e-098.254206637035775	21.415095022060235	30
700	20	4	60	e-098.552412545082786	21.445611641150606	31
1500	20	4	60	e-099.691901907410127	21.432221436811872	32
10000	20	4	60	e-099.852979368178293	21.597368879815980	33
300	20	4	70	e-099.606900274959095	21.449030823072505	34
700	20	4	70	e-099.931360597160332	21.580905305218970	35
1500	20	4	70	e-099.771556714628313	21.533666446488640	36
10000	20	4	70	e-081.025573935042055	21.710240037195483	37
300	20	4	100	e 1.011481866415225	21.792009294914347	38
700	20	4	100	e-081.113187414833491	21.867822159879612	39
1500	20	4	100	e-081.035333672534274	21.827532770079130	40
10000	20	4	100	e-081.176478654361470	22.017939492092140	41
300	20	4	500	e-081.871144283760800	23.246684368486726	42
700	20	4	500	e-081.915993552350869	23.272559820210603	43
1500	20	4	500	e-081.925908365806838	23.301261622120750	44
10000	20	4	500	e-081.954368329911922	23.295674831249430	45