ජාන ඇල්ගොරිතම (Genetic Algorithms - GA) | Dileenet A/L ICT

 

ජාන ඇල්ගොරිතම (Genetic Algorithms - GA)

 ගැටළු විසඳීම සඳහා භාවිතා කරන එක්තරා ආකාරයක සෙවුම් ඇල්ගොරිතමයකි. මෙම ඇල්ගොරිතම, ස්වභාවික වරණය (Natural Selection) සහ ජාන විද්‍යාව (Genetics) යන මූලධර්ම මත පදනම්ව නිර්මාණය කර ඇත. සංකීර්ණ ප්‍රශස්තකරණ (Optimization) ගැටළු විසඳීම සඳහා ඒවා බහුලව භාවිතා වේ.සරලව කිවහොත්, ගැටලුවකට හොඳම විසඳුම සොයා ගැනීම සඳහා පරිගණකයකින් "පරිණාමන" ක්‍රියාවලියක් අනුකරණය කිරීම මෙහිදී සිදු වේ.

මූලික පියවර සහ සංකල්ප:

1. ජනගහනයක් නිර්මාණය කිරීම (Initialization):
• විසඳුම් අපේක්ෂකයන් ගණනාවකින් යුත් මූලික "ජනගහනයක්" අහඹු ලෙස නිර්මාණය කරයි. සෑම විසඳුමක්ම "වර්ණදේහයක්" (Chromosome) ලෙස හැඳින්වේ.
2. යෝග්‍යතාවය තක්සේරු කිරීම (Fitness Evaluation):
• සෑම වර්ණදේහයක්ම (විසඳුමක්ම) ගැටලුවට කෙතරම් හොඳින් ගැලපේද යන්න තීරණය කිරීම සඳහා "යෝග්‍යතා ශ්‍රිතයක්" (Fitness Function) භාවිතා කරයි. ඉහළම යෝග්‍යතා ලකුණු ඇති ඒවා හොඳම විසඳුම් වේ.
3. වරණය (Selection):
• ඉහළ යෝග්‍යතා ලකුණු ඇති වර්ණදේහ (හොඳම විසඳුම්) ඊළඟ පරම්පරාව සඳහා තෝරා ගනු ලැබේ. ස්වභාවධර්මයේ මෙන්, "වඩා හොඳින් දිවි ගලවා ගන්නා" විසඳුම් තෝරා ගනී.
4. සංයෝජනය/සංකරණය (Crossover):
• තෝරාගත් වර්ණදේහ දෙකක් (දෙමාපියන්) ඒකාබද්ධ කරනු ලබන්නේ නව "දරුවෙකු" (විසඳුම් අපේක්ෂකයන්) නිර්මාණය කිරීම සඳහාය. මෙහිදී දෙමාපියන්ගේ ලක්ෂණ මිශ්‍ර වේ.
5. විපර්යාසය (Mutation):
• නව වර්ණදේහයේ අහඹු කොටසක් (ජාන කොටසක්) සුළු වශයෙන් වෙනස් කරනු ලැබේ. මෙය "නව" විසඳුම් ගවේෂණය කිරීමට සහ ඇල්ගොරිතම එකම විසඳුමක සිරවී සිටීම වැළැක්වීමට උපකාරී වේ.
6. නව පරම්පරාවක් (New Generation):
• සංකරණය සහ විපර්යාසය මගින් නිර්මාණය කරන ලද නව වර්ණදේහවලින් නව ජනගහනයක් සෑදේ.

මෙම ක්‍රියාවලිය නැවත නැවතත් සිදු කරනු ලබන්නේ හොඳම විසඳුම (වැඩිම යෝග්‍යතාවය සහිත වර්ණදේහය) සොයා ගන්නා තුරුය.

උදාහරණ යෙදීම්:

• සැලසුම් ප්‍රශස්තකරණය (Engineering Design Optimization)
• කාලසටහන් සකස් කිරීම (Timetabling)
• ගමන් කරන වෙළෙන්දාගේ ගැටලුව (Travelling Salesman Problem) වැනි සංකීර්ණ සෙවුම් ගැටළු.

සැබැවින්ම සරල ජාන ඇල්ගොරිතමයක් ක්‍රියා කරන ආකාරය පහත උදාහරණයෙන් පැහැදිලි කළ හැක.

ගැටලුව:

f(x)=x2 නම් ශ්‍රිතය (Function) භාවිතයෙන් 0 සහ 31 අතර ඇති වැඩිම අගය (Maximum Value) ලබා දෙන x හි අගය සොයා ගැනීම.

1. සංකේතනය (Encoding) - වර්ණදේහය (Chromosome)

• අපගේ විසඳුම් 0 සිට 31 දක්වා අංක වේ.
• 31 යනු ද්විමය ආකාරයෙන් බිටු 5 කින් (Binary, 5 bits) නිරූපණය කළ හැක.
• වර්ණදේහය (විසඳුම් අපේක්ෂකයා) බිටු 5 ක දාමයක් (String) වේ.
• උදා: x=13 යනු ද්විමය ආකාරයෙන් 01101 වේ.

2. මූලික ජනගහනය (Initial Population)

• අහඹු ලෙස වර්ණදේහ 4 කින් යුත් මූලික ජනගහනයක් නිර්මාණය කරමු:

වර්ණදේහය (ද්විමය)	x හි දශම අගය	f(x)=x2 (යෝග්‍යතාවය)
10100	20	400
01111	15	225
11000	24	576
00010	2	4

• හොඳම විසඳුම මේ වන විට: x=24 (f(x)=576)

3. වරණය (Selection) - දෙමාපියන් තෝරාගැනීම

• ඉහළම යෝග්‍යතා අගය (Fitness Value) ඇති වර්ණදේහ දෙමාපියන් ලෙස තෝරා ගනු ලැබේ.
• අපි 11000 (24) සහ 10100 (20) තෝරා ගනිමු.

 

4. සංයෝජනය (Crossover) - නව පරම්පරාව

• තෝරාගත් දෙමාපියන්ගේ ජාන මිශ්‍ර කිරීම:
• දෙමාපිය 1: 10100
• දෙමාපිය 2: 11000
• අහඹු ලෙස කඩන ස්ථානයක් (Crossover Point) තෝරමු, උදාහරණයක් ලෙස තුන්වන බිටුවට පසුව:

දෙමාපියන්	කැඩුණු කොටස්
$101 ,	, 00$
$110 ,	, 00$

• අපට නව දරුවන් දෙදෙනෙකු ලැබේ:
• දරුවා A (Child A): දෙමාපිය 1 හි මුල් කොටස + දෙමාපිය 2 හි දෙවන කොටස = 10100
• දරුවා B (Child B): දෙමාපිය 2 හි මුල් කොටස + දෙමාපිය 1 හි දෙවන කොටස = 11000

5. විපර්යාසය (Mutation)

• අහඹු ලෙස තෝරාගත් එක් බිටුවක් පෙරළීම (Flipping) (උදා: 0→1 හෝ 1→0)
• උදාහරණයක් ලෙස:
• දරුවා A වූ 10100 හි අවසාන බිටුව වෙනස් කරමු: 10101
• දරුවා B වූ 11000 හි සිව්වන බිටුව වෙනස් කරමු: 11010
• නව පරම්පරාව:
• දරුවා A: 10101 (x=21) →f(x)=441
• දරුවා B: 11010 (x=26) →f(x)=676

6. ප්‍රතිස්ථාපනය සහ පුනරාවර්තනය (Replacement and Iteration)

• දැන්, මුල් ජනගහනයෙන් යෝග්‍යතා අඩු වර්ණදේහ වෙනුවට මෙම නව දරුවන් දෙදෙනා ආදේශ කරනු ලැබේ.
• අපේ නව හොඳම විසඳුම වන්නේ x=26 (f(x)=676) ය. එය මුල් හොඳම අගය වන 576 ට වඩා හොඳයි!