توضیحات
A memetic algorithm for graph coloring
پروژه پردازش تکاملی بر روی مسئله رنگ امیزی گراف
در این مستند به گزارشی از چگونگی کارکد و کدنویسی مقاله پیشنهادی میپردازیم.
در ابتدا توابع برنامه را بررسی و توضیح خواهیم داد و سپس به بررسی بدنه اصلی برنامه و در نهایت نتایج را بررسی خواهیم کرد.
تابع imortfile :
این تابع از توابع نوشته شده توسط خود matlab است و وظیفه آن دریافت فایل ورودی و دادن سه فایل خروجی data، rowHeaders و textdata است.
در این برنامه فقط از خروجی data که در واقع ماتریس همسایگی گراف استفاده میشود.
این ماتریس دارای دو ستون و به تعداد همسایگیهای رئوس سطر دارد، بهطوری که در ستون اول شماره راس به ترتیب نزولی آمده است و در ستون دوم راس همسایه با راس ستون اول امده است.
همانطور که مشخص است از این تابع در خواندن داده لازم برای بررسی و تعیین تعداد رنگ استفاده میشود.
function [x v color_nodes] = initial(n,matrix,maxc)
تابع مقدار دهی اولیه جمعیت :
ورودی- تعدا رئوس – ماتریس مجاورت و حداکثر رنگ مجاز – خروجی : یک نمونه از جمعیت(x) – فراوانی تعداد رنگ ها(v) – راسهای هر رنگ
مقادیر ثابت پیشنهادی مقاله2
C=1;
k=1;
ku = 0.025;
ka = 0.33;
k1= 1;
k2= 1;
k3= 0.5;
k4 = 0.025;
x(1:n) = 0; رنگ کردن با رنگ صفرم همه رئوس
حلقه بررسی رئوس و رنگ آمیزی انان
for i=1:n
در این بخش براساس صفحات 2-7 مقاله 2، فرمول خطرناک بودن هر گراف محاسبه میشود.
…
در صورتی که یک راس همسایه ای نداشته باشد به عنوان راس بی خطر رنگ آمیزی میشود
در اینجا فقط نمونه ای از توضیحات کد متلب و گزارش کار اینجا آمده است.
برای دریافت شبیه سازی و گزارش کامل این شبیه سازی, باید این محصول را خریداری نمایید.
تعداد رنگهایی که برای راس موردنظر مجاز هستند بدون ایجاد تداخل
function res = available(x,matrix,node)
%find available colors for node ‘node’
num = ones(size(x,2),1);
[r c] = find(matrix(:,1) == node);
if(~isempty(r))
for i=1:length(r)
num(matrix(r(i),2)) = 0;
end
end
[r c] = find(num==1);
res = length(r);
end
تعداد رنگهای مجازی که هم برای همسایه و هم برای راس موردنظر موجود هستند
function res = Share(x,matrix,nodes)
%find available colors for node ‘node’
num = ones(size(x,2),1);
for itr=1:length(nodes)
[r c] = find(matrix(:,1) == nodes(itr));
if(~isempty(r))
for i=1:length(r)
num(matrix(r(i),2)) = 0;
end
end
end
[r c] = find(num==1);
res = length(r);
end
در ادامه به بررسی تابع جستجوی محلی tabu search میپردازیم:
function [x conf cl cl_detail val] = tabu(x,maxc,conf,cl,cl_detail,adj)
تابع جستجوی tabu وظیفه جستجوی محلی و بهتر کردن پاسخ فعلی است.
ورودی : x-رئوس و رنگهای آنها maxc-حداکثر رنگ موجود conf-ماتریس تداخل رئوس همرنگ cl-فراوانی رنگها cl_detail-هر اندیس در بردارنده رئوسی است که دراای رنگ شماره اندیس هستند. Adj-ماتریس مجاورت
خروجی : همان ورودی ها + val-ارزش راه حل(تعداد تداخل ها)
پارامترهای موجود در جدول زیر، پارامترهای در نظر گرفته شده برای حل مسائل مختلف است. همچنین نتیجه تست گراف DSJC125.1.col پس از 23 تکرار با 7 رنگ به نتیجه دلخواه رسید.
| اندازه جمعیت | 40 |
| عمق جستجوی تابو(تعداد تکرار بی تغیی) | 100000 |
| تعداد والدین در عملگر ترکیب | 2-6 ( انتخاب بهطور تصادفی) |
| پارامتر تخمین خوب بودن راه حل (λ) | 0.08 |
کلید واژه :,پروژه متلب,شبیه سازی با متلب,matlab project,پروژه های matlab,
Graph coloring, Memetic algorithm, Crossover operator, Pool updating
شبیه سازی
A memetic algorithm for graph coloring
به تعداد محدودی قابل فروش می باشد.
سفارش انجام پروژه مشابه
درصورتیکه این محصول دقیقا مطابق خواسته شما نمی باشد،.
با کلیک بر روی کلید زیر پروژه دلخواه خود را سفارش دهید.
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.