Evolutionary Algorithms (EA) หรือ อัลกอริทึมวิวัฒนาการ คือกลุ่มอัลกอริทึมที่ได้รับแรงบันดาลใจจากกระบวนการวิวัฒนาการตามธรรมชาติ (Natural Evolution) ตามทฤษฎีของชาร์ลส์ ดาร์วิน (Charles Darwin) โดยอาศัยหลักการ "ผู้แข็งแกร่งกว่าอยู่รอด" (Survival of the Fittest)
แนวคิดหลักคือ การค้นหาคำตอบที่ดีที่สุด (Optimal Solution) สำหรับปัญหาที่ซับซ้อน ด้วยการจำลองกระบวนการวิวัฒนาการผ่านประชากรของผู้สมัคร (Population of Candidates) ที่ปรับตัวดีขึ้นในแต่ละรุ่น (Generation)
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#282828', 'primaryTextColor': '#ebdbb2', 'primaryBorderColor': '#fabd2f', 'lineColor': '#83a598', 'secondaryColor': '#3c3836', 'tertiaryColor': '#504945', 'background': '#282828', 'mainBkg': '#282828', 'nodeBorder': '#fabd2f', 'clusterBkg': '#3c3836', 'titleColor': '#ebdbb2', 'edgeLabelBackground': '#3c3836', 'attributeBackgroundColorEven': '#282828', 'attributeBackgroundColorOdd': '#3c3836'}}}%%
flowchart TD
subgraph era1["🕰️ ยุคบุกเบิก (1950s-1960s)"]
A1["1954: Nils Barricelli - การทดลอง Numerical Evolution - ด้วยคอมพิวเตอร์ IAS"]
A2["1962: John Holland - เริ่มงานวิจัย Adaptive Systems - ที่ University of Michigan"]
A3["1964: Ingo Rechenberg - พัฒนา Evolution Strategies - ใน TU Berlin"]
end
subgraph era2["🔬 ยุคพัฒนา (1970s-1980s)"]
B1["1975: John Holland - ตีพิมพ์ 'Adaptation in Natural - and Artificial Systems'"]
B2["1975: David Fogel - พัฒนา Evolutionary Programming"]
B3["1989: David Goldberg - ตีพิมพ์ Genetic Algorithms - in Search, Optimization, and ML"]
end
subgraph era3["🌐 ยุครุ่งเรือง (1990s-2000s)"]
C1["1992: John Koza - พัฒนา Genetic Programming"]
C2["1995: James Kennedy & Russell Eberhart - พัฒนา Particle Swarm Optimization"]
C3["1999: Marco Dorigo - พัฒนา Ant Colony Optimization"]
end
subgraph era4["🚀 ยุคปัจจุบัน (2010s-Now)"]
D1["2012: DEAP Library - ออกแบบ EA Framework ที่ยืดหยุ่น"]
D2["2017-Now: Neuroevolution - ผสาน EA กับ Deep Learning - เช่น NEAT, CMA-ES"]
D3["2020-Now: EA in AutoML - ใช้สำหรับ Neural Architecture Search"]
end
era1 --> era2 --> era3 --> era4
style era1 fill:#3c3836,stroke:#fabd2f,color:#ebdbb2
style era2 fill:#3c3836,stroke:#b8bb26,color:#ebdbb2
style era3 fill:#3c3836,stroke:#83a598,color:#ebdbb2
style era4 fill:#3c3836,stroke:#d3869b,color:#ebdbb2
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#282828', 'primaryTextColor': '#ebdbb2', 'primaryBorderColor': '#fabd2f', 'lineColor': '#83a598', 'secondaryColor': '#3c3836', 'tertiaryColor': '#504945'}}}%%
mindmap
root((Evolutionary Computation
การคำนวณเชิงวิวัฒนาการ))
GA[Genetic Algorithms
อัลกอริทึมพันธุกรรม]
Binary Encoding
Real-valued Encoding
Selection Methods
Crossover & Mutation
GP[Genetic Programming
โปรแกรมพันธุกรรม]
Tree Representation
Program Evolution
Symbolic Regression
ES[Evolution Strategies
กลยุทธ์วิวัฒนาการ]
Self-adaptation
CMA-ES
μ+λ Strategy
SI[Swarm Intelligence
ความฉลาดฝูงชน]
PSO Particle Swarm
ACO Ant Colony
Bee Algorithm
Genetic Algorithm (GA) คืออัลกอริทึมการค้นหาและปรับแต่ง (Search & Optimization) ที่จำลองกระบวนการคัดเลือกตามธรรมชาติ โดยทำงานกับประชากรของ Chromosome (โครโมโซม) ซึ่งแต่ละตัวแทนคำตอบที่เป็นไปได้ (Candidate Solution)
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#282828', 'primaryTextColor': '#ebdbb2', 'primaryBorderColor': '#fabd2f', 'lineColor': '#83a598', 'secondaryColor': '#3c3836'}}}%%
flowchart TD
A(["🧬 เริ่มต้น - Initialization - สร้างประชากรเริ่มต้น"])
B["📊 ประเมินความเหมาะสม - Fitness Evaluation - คำนวณค่า Fitness แต่ละตัว"]
C{{"🏁 เงื่อนไขหยุด? - Termination - Condition?"}}
D["🎯 คัดเลือกผู้รอดชีวิต - Selection - Roulette / Tournament"]
E["✂️ ไขว้สาย - Crossover - แลกเปลี่ยนยีน"]
F["🔀 กลายพันธุ์ - Mutation - เปลี่ยน Gene แบบสุ่ม"]
G["👥 สร้างรุ่นใหม่ - New Generation - แทนที่ประชากรเก่า"]
H(["✅ คำตอบที่ดีที่สุด - Best Solution - Output"])
A --> B --> C
C -- "❌ ยังไม่หยุด" --> D
C -- "✅ หยุด" --> H
D --> E --> F --> G --> B
style A fill:#98971a,stroke:#b8bb26,color:#282828
style H fill:#98971a,stroke:#b8bb26,color:#282828
style C fill:#cc241d,stroke:#fb4934,color:#ebdbb2
style B fill:#458588,stroke:#83a598,color:#ebdbb2
style D fill:#d65d0e,stroke:#fe8019,color:#282828
style E fill:#b16286,stroke:#d3869b,color:#ebdbb2
style F fill:#689d6a,stroke:#8ec07c,color:#282828
style G fill:#3c3836,stroke:#fabd2f,color:#ebdbb2
การเข้ารหัสคือการแปลงคำตอบของปัญหา (Solution) ให้อยู่ในรูปแบบ Chromosome ที่ GA สามารถทำงานได้
Binary Encoding แทนคำตอบด้วยสายบิต 0 และ 1 เหมาะกับปัญหาแบบ Combinatorial Optimization
ตัวอย่าง: ปัญหา Knapsack (กระเป๋าเดินทาง) — มีสินค้า 5 ชิ้น แต่ละบิตบอกว่าใส่ (1) หรือไม่ใส่ (0)
Chromosome: [1, 0, 1, 1, 0]
↑ ↑ ↑ ↑ ↑
ชิ้น1 ชิ้น2 ชิ้น3 ชิ้น4 ชิ้น5
ความหมาย: ใส่ชิ้นที่ 1, 3, 4 ไม่ใส่ชิ้นที่ 2, 5
Real-valued Encoding แทน Gene ด้วยจำนวนทศนิยม เหมาะกับปัญหา Continuous Optimization
ตัวอย่าง: หา Parameters ของฟังก์ชัน Neural Network
Chromosome: [0.42, -1.73, 2.15, 0.89, -0.31]
w₁ w₂ w₃ w₄ bias
| การเข้ารหัส | ข้อดี | ข้อเสีย | เหมาะกับปัญหา |
|---|---|---|---|
| Binary | ง่าย, เป็นมาตรฐาน | ต้องการบิตมากสำหรับความแม่นยำสูง | Combinatorial, 0/1 decisions |
| Real-valued | ความแม่นยำสูง, เป็นธรรมชาติ | Mutation ต้องออกแบบดี | Continuous optimization |
| Permutation | เหมาะกับการจัดลำดับ | Crossover ซับซ้อน | TSP, Scheduling |
| Tree | ยืดหยุ่น, แทน Programs | ขนาดไม่แน่นอน | Genetic Programming |
Fitness Function คือฟังก์ชันที่วัดว่า Chromosome แต่ละตัว "ดี" แค่ไหน เป็นตัวบอกทิศทางของการวิวัฒนาการ
ข้อมูลตัวอย่าง:
| สินค้า | น้ำหนัก (kg) | มูลค่า (บาท) |
|---|---|---|
| A (มือถือ) | 1 | 5,000 |
| B (แล็ปท็อป) | 4 | 20,000 |
| C (กล้อง) | 3 | 12,000 |
| D (หนังสือ) | 1 | 2,000 |
| E (ชุดเสื้อผ้า) | 2 | 3,000 |
ความจุกระเป๋า: 6 kg
คำนวณ Fitness สำหรับ Chromosome [1,1,0,1,0]:
สมการ Fitness:
โดยที่:
แนวคิด: แต่ละ Chromosome มีโอกาสถูกเลือกตามสัดส่วน Fitness
สมการความน่าจะเป็นในการเลือก:
ตัวอย่างการคำนวณ:
ประชากร 4 ตัวกับค่า Fitness:
| Chromosome | Fitness | โอกาส (%) |
|---|---|---|
| [1,0,1,1,0] | 27,000 | 27,000/67,000 = 40.3% |
| [0,1,0,1,1] | 25,000 | 25,000/67,000 = 37.3% |
| [1,0,0,1,0] | 7,000 | 7,000/67,000 = 10.4% |
| [0,0,1,1,0] | 8,000 | 8,000/67,000 = 11.9% |
| รวม | 67,000 | 100% |
การหมุนวงล้อ → จำลองด้วยเลขสุ่ม r ∈ [0, 1]:
แนวคิด: สุ่มเลือก k ตัวมาแข่งขัน แล้วเลือกตัวที่ดีที่สุด
Tournament Size k=3:
1. สุ่มเลือก: [1,0,1,1,0], [0,0,1,1,0], [0,1,0,1,1]
2. เปรียบ Fitness: 27,000 vs 8,000 vs 25,000
3. ผู้ชนะ: [1,0,1,1,0] (Fitness = 27,000)
Single-Point Crossover:
Parent 1: [1, 0, 1 | 1, 0]
Parent 2: [0, 1, 0 | 1, 1]
↕ cut point = 3
Child 1: [1, 0, 1 | 1, 1]
Child 2: [0, 1, 0 | 1, 0]
Two-Point Crossover:
Parent 1: [1 | 0, 1, 1 | 0]
Parent 2: [0 | 1, 0, 1 | 1]
↕ cut at 1, 4 ↕
Child 1: [1 | 1, 0, 1 | 0]
Child 2: [0 | 0, 1, 1 | 1]
Uniform Crossover:
Mask: [1, 0, 1, 0, 1]
Parent 1: [1, 0, 1, 1, 0]
Parent 2: [0, 1, 0, 1, 1]
Child 1: [1, 1, 1, 1, 1] ← mask=1: ใช้ P1, mask=0: ใช้ P2
สมการอัตรา Mutation:
โดยที่ L = ความยาวของ Chromosome (แนะนำโดย John Holland)
Bit-flip Mutation (สำหรับ Binary):
ก่อน Mutation: [1, 0, 1, 1, 0]
↑ mutate bit 4
หลัง Mutation: [1, 0, 1, 0, 0]
Gaussian Mutation (สำหรับ Real-valued):
ก่อน: [0.42, -1.73, 2.15]
หลัง: [0.42, -1.73+N(0,σ), 2.15] = [0.42, -1.51, 2.15]
"""
อัลกอริทึมพันธุกรรม (Genetic Algorithm) สำหรับปัญหา Knapsack
ใช้ DEAP Library (Distributed Evolutionary Algorithms in Python)
การติดตั้ง: pip install deap matplotlib numpy
"""
import random
import numpy as np
import matplotlib.pyplot as plt
from deap import algorithms, base, creator, tools
# ========== ข้อมูลปัญหา Knapsack ==========
ITEMS = {
'มือถือ': {'weight': 1, 'value': 5000},
'แล็ปท็อป': {'weight': 4, 'value': 20000},
'กล้อง': {'weight': 3, 'value': 12000},
'หนังสือ': {'weight': 1, 'value': 2000},
'ชุดเสื้อผ้า': {'weight': 2, 'value': 3000},
'หูฟัง': {'weight': 1, 'value': 4000},
'แท็บเล็ต': {'weight': 2, 'value': 8000},
'ร่มกันฝน': {'weight': 1, 'value': 1000},
}
ITEM_NAMES = list(ITEMS.keys())
WEIGHTS = [ITEMS[name]['weight'] for name in ITEM_NAMES]
VALUES = [ITEMS[name]['value'] for name in ITEM_NAMES]
MAX_WEIGHT = 8 # ความจุกระเป๋า (kg)
N_ITEMS = len(ITEMS)
# ========== ฟังก์ชัน Fitness ==========
def evaluate_knapsack(individual):
"""
คำนวณ Fitness ของ Chromosome
Args:
individual: list of 0/1 แทนการเลือกสินค้าแต่ละชิ้น
Returns:
tuple: (total_value,) — DEAP ต้องการ tuple
"""
total_weight = sum(w * x for w, x in zip(WEIGHTS, individual))
total_value = sum(v * x for v, x in zip(VALUES, individual))
# Penalty สำหรับน้ำหนักเกิน
if total_weight > MAX_WEIGHT:
# หักค่าเพิ่มตามที่เกิน
penalty = (total_weight - MAX_WEIGHT) * 10000
return (max(0, total_value - penalty),)
return (total_value,)
# ========== ตั้งค่า DEAP ==========
# สร้าง Fitness Class (maximize)
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
toolbox = base.Toolbox()
# Gene: 0 หรือ 1
toolbox.register("attr_bool", random.randint, 0, 1)
# Individual: list ของ genes ขนาด N_ITEMS
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_bool, n=N_ITEMS)
# Population: list ของ individuals
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
# ลงทะเบียน operators
toolbox.register("evaluate", evaluate_knapsack)
toolbox.register("mate", tools.cxTwoPoint) # Two-point Crossover
toolbox.register("mutate", tools.mutFlipBit, indpb=1/N_ITEMS) # Bit-flip Mutation
toolbox.register("select", tools.selTournament, tournsize=3) # Tournament Selection
# ========== รัน GA ==========
def run_ga(population_size=100, n_generations=50,
crossover_prob=0.8, mutation_prob=0.2, seed=42):
"""
รัน Genetic Algorithm
Args:
population_size: จำนวนประชากร
n_generations: จำนวนรุ่น
crossover_prob: ความน่าจะเป็น Crossover
mutation_prob: ความน่าจะเป็น Mutation
seed: Random seed
Returns:
best_individual: Chromosome ที่ดีที่สุด
log: ประวัติ Statistics
"""
random.seed(seed)
np.random.seed(seed)
# สร้างประชากรเริ่มต้น
population = toolbox.population(n=population_size)
# สถิติที่ต้องการเก็บ
stats = tools.Statistics(lambda ind: ind.fitness.values[0])
stats.register("avg", np.mean)
stats.register("max", np.max)
stats.register("min", np.min)
# Hall of Fame — เก็บ best individual
hof = tools.HallOfFame(1)
# รัน Evolutionary Algorithm (μ + λ style)
final_pop, log = algorithms.eaSimple(
population,
toolbox,
cxpb = crossover_prob,
mutpb = mutation_prob,
ngen = n_generations,
stats = stats,
halloffame = hof,
verbose = False
)
return hof[0], log
# ========== แสดงผลลัพธ์ ==========
def display_result(best_individual):
"""แสดงผลสินค้าที่เลือกจาก Chromosome ที่ดีที่สุด"""
print(" - " + "="*50)
print("🏆 ผลลัพธ์ที่ดีที่สุด")
print("="*50)
selected_items = []
total_weight = 0
total_value = 0
for i, (name, selected) in enumerate(zip(ITEM_NAMES, best_individual)):
if selected:
item = ITEMS[name]
selected_items.append(name)
total_weight += item['weight']
total_value += item['value']
print(f" ✅ {name:15} น้ำหนัก: {item['weight']} kg "
f"มูลค่า: {item['value']:,} บาท")
print(f" - 📦 น้ำหนักรวม : {total_weight}/{MAX_WEIGHT} kg")
print(f" 💰 มูลค่ารวม : {total_value:,} บาท")
print(f" 🧬 Chromosome : {list(best_individual)}")
def plot_evolution(log):
"""วาดกราฟแสดงความก้าวหน้าของวิวัฒนาการ"""
generations = [entry['gen'] for entry in log]
avg_fitness = [entry['avg'] for entry in log]
max_fitness = [entry['max'] for entry in log]
min_fitness = [entry['min'] for entry in log]
plt.figure(figsize=(10, 6))
plt.plot(generations, max_fitness, 'g-o', label='Maximum Fitness',
linewidth=2, markersize=4)
plt.plot(generations, avg_fitness, 'b-s', label='Average Fitness',
linewidth=2, markersize=4)
plt.plot(generations, min_fitness, 'r-^', label='Minimum Fitness',
linewidth=2, markersize=4)
plt.fill_between(generations, min_fitness, max_fitness,
alpha=0.15, color='blue')
plt.xlabel('Generation (รุ่น)', fontsize=12)
plt.ylabel('Fitness Value (มูลค่า บาท)', fontsize=12)
plt.title('การวิวัฒนาการของ Genetic Algorithm - Knapsack Problem', fontsize=14)
plt.legend(fontsize=11)
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('ga_evolution.png', dpi=150, bbox_inches='tight')
plt.show()
print(" - 💾 บันทึกกราฟเป็น ga_evolution.png")
# ========== ตัวอย่างการใช้งาน ==========
if __name__ == "__main__":
print("🧬 Genetic Algorithm: Knapsack Problem")
print(f"📋 สินค้าทั้งหมด {N_ITEMS} ชิ้น, ความจุ {MAX_WEIGHT} kg - ")
# รัน GA
best, log = run_ga(
population_size = 100,
n_generations = 50,
crossover_prob = 0.8,
mutation_prob = 0.2
)
# แสดงผล
display_result(best)
plot_evolution(log)
ผลลัพธ์ที่คาดหวัง:
🧬 Genetic Algorithm: Knapsack Problem
📋 สินค้าทั้งหมด 8 ชิ้น, ความจุ 8 kg
==================================================
🏆 ผลลัพธ์ที่ดีที่สุด
==================================================
✅ มือถือ น้ำหนัก: 1 kg มูลค่า: 5,000 บาท
✅ แล็ปท็อป น้ำหนัก: 4 kg มูลค่า: 20,000 บาท
✅ หูฟัง น้ำหนัก: 1 kg มูลค่า: 4,000 บาท
✅ แท็บเล็ต น้ำหนัก: 2 kg มูลค่า: 8,000 บาท
📦 น้ำหนักรวม : 8/8 kg
💰 มูลค่ารวม : 37,000 บาท
Genetic Programming (GP) เป็นส่วนขยายของ GA ที่วิวัฒนาการ โปรแกรมหรือสูตรคณิตศาสตร์ แทนที่จะเป็นแค่ค่าพารามิเตอร์ Chromosome ถูกแทนด้วย Tree Structure
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#282828', 'primaryTextColor': '#ebdbb2', 'primaryBorderColor': '#fabd2f', 'lineColor': '#83a598', 'secondaryColor': '#3c3836'}}}%%
graph TD
R(["➕ +"])
A(["✖️ *"])
B(["➗ /"])
C(["x"])
D(["2.5"])
E(["sin"])
F(["y"])
R --> A
R --> B
A --> C
A --> D
B --> E
B --> F
E --> F
style R fill:#cc241d,stroke:#fb4934,color:#ebdbb2
style A fill:#d65d0e,stroke:#fe8019,color:#282828
style B fill:#d65d0e,stroke:#fe8019,color:#282828
style C fill:#458588,stroke:#83a598,color:#ebdbb2
style D fill:#458588,stroke:#83a598,color:#ebdbb2
style E fill:#689d6a,stroke:#8ec07c,color:#282828
style F fill:#458588,stroke:#83a598,color:#ebdbb2
สมการที่ Tree นี้แทน:
"""
Genetic Programming สำหรับ Symbolic Regression
หาสมการที่ fit กับข้อมูล โดยไม่ต้องรู้โครงสร้างสมการล่วงหน้า
การติดตั้ง: pip install deap numpy matplotlib
"""
import operator
import math
import random
import numpy as np
import matplotlib.pyplot as plt
from deap import algorithms, base, creator, gp, tools
# ========== สร้างชุดข้อมูล (ความจริงคือ f(x) = x² + x - 6) ==========
def target_function(x):
"""ฟังก์ชันเป้าหมายที่เราต้องการให้ GP ค้นพบ"""
return x**2 + x - 6
np.random.seed(42)
X_data = np.linspace(-5, 5, 50) # จุดข้อมูล 50 จุด
y_data = target_function(X_data) + np.random.normal(0, 0.5, 50) # เพิ่ม noise
# ========== กำหนด Primitive Set (ตัวดำเนินการที่ GP ใช้ได้) ==========
def protected_div(a, b):
"""การหารที่ป้องกัน division by zero"""
return a / b if abs(b) > 1e-9 else 1.0
pset = gp.PrimitiveSet("MAIN", arity=1) # 1 input variable (x)
pset.addPrimitive(operator.add, 2) # บวก
pset.addPrimitive(operator.sub, 2) # ลบ
pset.addPrimitive(operator.mul, 2) # คูณ
pset.addPrimitive(protected_div, 2) # หาร
pset.addEphemeralConstant("rand", lambda: round(random.uniform(-5, 5), 2))
pset.renameArguments(ARG0='x') # เปลี่ยนชื่อ argument เป็น x
# ========== ตั้งค่า DEAP สำหรับ GP ==========
creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) # minimize error
creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=3)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("compile", gp.compile, pset=pset)
def evaluate_gp(individual):
"""คำนวณ Mean Squared Error ของสมการที่วิวัฒนาการ"""
func = toolbox.compile(expr=individual)
try:
y_pred = np.array([func(x) for x in X_data])
mse = np.mean((y_pred - y_data) ** 2)
return (mse,)
except:
return (float('inf'),)
toolbox.register("evaluate", evaluate_gp)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", gp.cxOnePoint)
toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
toolbox.register("mutate", gp.mutUniform, expr=toolbox.expr_mut, pset=pset)
# จำกัดความลึกของ Tree (ป้องกัน Bloat)
toolbox.decorate("mate", gp.staticLimit(key=operator.attrgetter("height"), max_value=8))
toolbox.decorate("mutate", gp.staticLimit(key=operator.attrgetter("height"), max_value=8))
# ========== รัน GP ==========
def run_gp():
random.seed(42)
population = toolbox.population(n=300)
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values[0])
stats.register("avg", lambda x: round(np.mean(x), 4))
stats.register("min", lambda x: round(np.min(x), 4))
final_pop, log = algorithms.eaSimple(
population, toolbox,
cxpb=0.7, mutpb=0.2, ngen=40,
stats=stats, halloffame=hof, verbose=True
)
return hof[0], log
# ========== ตัวอย่างการใช้งาน ==========
if __name__ == "__main__":
print("🌳 Genetic Programming: Symbolic Regression")
print(f"🎯 เป้าหมาย: f(x) = x² + x - 6 - ")
best_expr, log = run_gp()
print(f" - ✅ สมการที่ค้นพบ: {str(best_expr)}")
print(f"📊 MSE: {best_expr.fitness.values[0]:.6f}")
# วาดกราฟเปรียบเทียบ
func = gp.compile(best_expr, pset=gp.PrimitiveSet("MAIN", arity=1))
# ... plotting code
Evolution Strategies (ES) เป็นอัลกอริทึมวิวัฒนาการที่ออกแบบมาสำหรับ Continuous Optimization โดยเฉพาะ พัฒนาโดย Ingo Rechenberg และ Hans-Paul Schwefel ที่ TU Berlin ในช่วงทศวรรษ 1960-70
โดยที่:
CMA-ES เป็นหนึ่งใน ES ที่ทรงพลังที่สุด ปรับ Covariance Matrix เพื่อเรียนรู้รูปร่างของ Fitness Landscape
สมการการสร้าง Offspring:
โดยที่:
"""
CMA-ES: Covariance Matrix Adaptation Evolution Strategy
แก้ปัญหา Sphere Function: minimize f(x) = Σxᵢ²
การติดตั้ง: pip install deap numpy
"""
import numpy as np
from deap import algorithms, base, benchmarks, cma, creator, tools
# ========== ตั้งค่า Problem ==========
N_DIM = 10 # จำนวนมิติ
def sphere_function(individual):
"""
Sphere Function: f(x) = Σxᵢ²
ค่าต่ำสุดที่ทฤษฎีคือ 0 เมื่อ x = [0,0,...,0]
"""
return (sum(x**2 for x in individual),)
# ========== ตั้งค่า DEAP CMA-ES ==========
creator.create("FitnessMin2", base.Fitness, weights=(-1.0,))
creator.create("Individual2", list, fitness=creator.FitnessMin2)
# ค่าเริ่มต้น: ตำแหน่งเริ่มต้น centroid และ step-size sigma
centroid = [5.0] * N_DIM # เริ่มจากจุดห่างจาก optimal มาก
sigma = 3.0 # step-size เริ่มต้น
strategy = cma.Strategy(centroid=centroid, sigma=sigma, lambda_=20)
toolbox = base.Toolbox()
toolbox.register("generate", strategy.generate, creator.Individual2)
toolbox.register("update", strategy.update)
toolbox.register("evaluate", sphere_function)
# ========== รัน CMA-ES ==========
def run_cmaes(n_generations=200):
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values[0])
stats.register("avg", np.mean)
stats.register("min", np.min)
# ใช้ eaGenerateUpdate algorithm
final_pop, log = algorithms.eaGenerateUpdate(
toolbox,
ngen = n_generations,
stats = stats,
halloffame = hof,
verbose = False
)
return hof[0], log
if __name__ == "__main__":
print("🎯 CMA-ES: Minimizing Sphere Function")
print(f"📐 มิติ: {N_DIM}D, จุดเริ่มต้น: {centroid[0]} (ทุกมิติ)")
best, log = run_cmaes(n_generations=200)
print(f" - ✅ ผลลัพธ์:")
print(f" ค่าที่ดีที่สุด (Best Fitness): {best.fitness.values[0]:.8f}")
print(f" x ≈ {[round(v, 4) for v in best[:5]]}... (แสดงแค่ 5 มิติแรก)")
print(f" ค่าทฤษฎีที่ดีที่สุด: 0.0 ที่ x=[0,...,0]")
Swarm Intelligence (SI) ได้รับแรงบันดาลใจจากพฤติกรรมรวมกลุ่มของสิ่งมีชีวิต เช่น ฝูงนก, ฝูงปลา, หรืออาณาจักรมด โดยแต่ละตัวมีพฤติกรรมง่ายๆ แต่รวมกันสร้างพฤติกรรมที่ฉลาดและซับซ้อน
PSO พัฒนาโดย Kennedy & Eberhart (1995) จำลองพฤติกรรมของฝูงนกที่ค้นหาอาหาร แต่ละ Particle แทนคำตอบที่เป็นไปได้ และเรียนรู้จาก:
อัปเดต Velocity:
อัปเดต Position:
โดยที่:
ปัญหา: หาค่าต่ำสุดของ f(x) = x² - 4x + 4 = (x-2)² คำตอบที่แท้จริง: x = 2, f(2) = 0
ประชากร 2 Particles:
| Particle | x₀ | v₀ | pbest |
|---|---|---|---|
| P1 | 0.0 | 1.0 | 0.0 |
| P2 | 5.0 | -1.5 | 5.0 |
gbest = P1 (f(0) = 4 < f(5) = 9) → gbest = 0.0
Iteration 1 (ω=0.7, c1=c2=2.0, r1=0.6, r2=0.4):
P1 update:
P2 update:
gbest อัปเดต: P1 ที่ x=0.7 → f(0.7) = 1.69 เป็น gbest ใหม่
ACO พัฒนาโดย Marco Dorigo (1992) จำลองพฤติกรรมมดที่หาทางสั้นที่สุดโดยใช้ Pheromone (สารเคมี)
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#282828', 'primaryTextColor': '#ebdbb2', 'primaryBorderColor': '#fabd2f', 'lineColor': '#fabd2f', 'secondaryColor': '#3c3836'}}}%%
flowchart LR
A(["🐜 มดออกจากรัง - Ants Leave - Nest"])
B["🔀 เลือกเส้นทาง - Path Selection - ตาม Pheromone + Heuristic"]
C["🏁 ถึงอาหาร - Reach - Food Source"]
D["💧 วาง Pheromone - Deposit Pheromone - ตามระยะทาง"]
E["⬇️ Pheromone ระเหย - Evaporation - τ ← (1-ρ)τ"]
F{"🔄 รอบถัดไป - Next Iteration"}
A --> B --> C --> D --> E --> F
F -- "ยังไม่ครบรอบ" --> A
F -- "ครบรอบแล้ว" --> G(["✅ เส้นทางที่ดีที่สุด - Best Path"])
style A fill:#689d6a,stroke:#8ec07c,color:#282828
style C fill:#458588,stroke:#83a598,color:#ebdbb2
style D fill:#b16286,stroke:#d3869b,color:#ebdbb2
style E fill:#cc241d,stroke:#fb4934,color:#ebdbb2
style G fill:#98971a,stroke:#b8bb26,color:#282828
สมการการเลือกเส้นทาง (Probability Rule):
โดยที่:
สมการ Evaporation:
โดยที่ ρ = อัตราการระเหย (Evaporation Rate) ∈ [0,1]
"""
Particle Swarm Optimization (PSO)
แก้ปัญหาการหาค่าต่ำสุดของ Rastrigin Function — ฟังก์ชันทดสอบ multimodal ยอดนิยม
การติดตั้ง: pip install numpy matplotlib
"""
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
# ========== ฟังก์ชันเป้าหมาย ==========
def rastrigin(x):
"""
Rastrigin Function — ปัญหา multimodal ที่ยากมาก
f(x) = An + Σ[xᵢ² - A*cos(2π*xᵢ)] โดย A=10
ค่าต่ำสุด = 0 ที่ x = [0, 0, ..., 0]
"""
A = 10
n = len(x)
return A * n + sum(xi**2 - A * np.cos(2 * np.pi * xi) for xi in x)
# ========== PSO Class ==========
class PSO:
"""
Particle Swarm Optimization
Parameters:
func: ฟังก์ชันที่ต้องการหาค่าต่ำสุด
n_particles: จำนวน particles
n_dims: จำนวนมิติ
bounds: ขอบเขต [(min, max)] ต่อมิติ
omega: inertia weight
c1, c2: acceleration coefficients
max_iter: จำนวน iterations สูงสุด
"""
def __init__(self, func, n_particles=30, n_dims=2,
bounds=(-5.12, 5.12), omega=0.729,
c1=1.494, c2=1.494, max_iter=100):
self.func = func
self.n_particles = n_particles
self.n_dims = n_dims
self.bounds = bounds
self.omega = omega
self.c1, self.c2 = c1, c2
self.max_iter = max_iter
# สร้างประชากรเริ่มต้น
low, high = bounds
self.pos = np.random.uniform(low, high, (n_particles, n_dims)) # positions
self.vel = np.random.uniform(-1, 1, (n_particles, n_dims)) # velocities
# pbest = ตำแหน่งที่ดีที่สุดของแต่ละ particle
self.pbest = self.pos.copy()
self.pbest_cost = np.array([func(p) for p in self.pbest])
# gbest = ตำแหน่งที่ดีที่สุดทั้งฝูง
best_idx = np.argmin(self.pbest_cost)
self.gbest = self.pbest[best_idx].copy()
self.gbest_cost = self.pbest_cost[best_idx]
# เก็บประวัติ
self.history = []
def optimize(self):
"""รัน PSO optimization"""
for iteration in range(self.max_iter):
# สร้าง random factors
r1 = np.random.rand(self.n_particles, self.n_dims)
r2 = np.random.rand(self.n_particles, self.n_dims)
# อัปเดต Velocity
cognitive = self.c1 * r1 * (self.pbest - self.pos)
social = self.c2 * r2 * (self.gbest - self.pos)
self.vel = self.omega * self.vel + cognitive + social
# จำกัด velocity
max_vel = 0.5 * (self.bounds[1] - self.bounds[0])
self.vel = np.clip(self.vel, -max_vel, max_vel)
# อัปเดต Position
self.pos = self.pos + self.vel
self.pos = np.clip(self.pos, self.bounds[0], self.bounds[1])
# ประเมิน Fitness
costs = np.array([self.func(p) for p in self.pos])
# อัปเดต pbest
improved = costs < self.pbest_cost
self.pbest[improved] = self.pos[improved].copy()
self.pbest_cost[improved] = costs[improved]
# อัปเดต gbest
best_idx = np.argmin(self.pbest_cost)
if self.pbest_cost[best_idx] < self.gbest_cost:
self.gbest = self.pbest[best_idx].copy()
self.gbest_cost = self.pbest_cost[best_idx]
self.history.append(self.gbest_cost)
if (iteration + 1) % 20 == 0:
print(f" Iteration {iteration+1:3d}: gbest = {self.gbest_cost:.6f}")
return self.gbest, self.gbest_cost
# ========== ตัวอย่างการใช้งาน ==========
if __name__ == "__main__":
print("🐦 Particle Swarm Optimization")
print("🎯 ปัญหา: Minimize Rastrigin Function (2D)")
print(" f(x,y) = 20 + x²-10cos(2πx) + y²-10cos(2πy)")
print(" ค่าต่ำสุดที่ทฤษฎี = 0 ที่ (x,y) = (0,0) - ")
np.random.seed(42)
pso = PSO(
func = rastrigin,
n_particles = 50,
n_dims = 2,
bounds = (-5.12, 5.12),
omega = 0.729,
c1 = 1.494,
c2 = 1.494,
max_iter = 100
)
best_pos, best_cost = pso.optimize()
print(f" - ✅ ผลลัพธ์:")
print(f" ตำแหน่งที่ดีที่สุด: x={best_pos[0]:.6f}, y={best_pos[1]:.6f}")
print(f" ค่าต่ำสุดที่พบ: f(x,y) = {best_cost:.6f}")
print(f" ค่าทฤษฎี: f(0,0) = 0.000000")
# วาดกราฟ Convergence
plt.figure(figsize=(10, 5))
plt.plot(pso.history, 'b-', linewidth=2)
plt.xlabel('Iteration (รอบ)')
plt.ylabel('Best Fitness (ค่า Rastrigin)')
plt.title('PSO Convergence on Rastrigin Function')
plt.yscale('log')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('pso_convergence.png', dpi=150)
plt.show()
| คุณสมบัติ | Genetic Algorithm | Evolution Strategy | Genetic Programming | PSO | ACO |
|---|---|---|---|---|---|
| การแทน Solution | Binary/Real Vector | Real Vector | Tree | Real Vector | Path |
| ประเภทปัญหา | Discrete/Continuous | Continuous | Symbolic | Continuous | Combinatorial |
| จุดเด่น | ยืดหยุ่น, ใช้ได้กว้าง | เก่งปัญหา Continuous | ค้นพบโครงสร้าง | เร็ว, Parameters น้อย | เหมาะ Network/Path |
| จุดด้อย | ต้องออกแบบ Encoding | เฉพาะ Real-valued | Tree ขยายใหญ่ | ติด Local Optima | Convergence ช้า |
| Hyperparameters | Pop size, pc, pm | μ, λ, σ | Pop size, tree depth | n, ω, c1, c2 | n_ants, α, β, ρ |
| Python Library | DEAP, PyGAD | DEAP, CMA | DEAP | pyswarms | ACOpy |
| Applications | Job scheduling, Feature selection | Neural network tuning | Automated formula discovery | Function optimization | TSP, VRP |
ทฤษฎี "ไม่มีอาหารกลางวันฟรี" (No Free Lunch Theorem) โดย Wolpert & Macready (1997) กล่าวว่า:
ไม่มีอัลกอริทึมใดดีที่สุดสำหรับทุกปัญหา การเปรียบเทียบค่าเฉลี่ยประสิทธิภาพบนปัญหาทุกชนิดจะได้เท่ากันสำหรับทุก algorithm
ผลกระทบในทางปฏิบัติ: ต้องทดสอบหลาย algorithm และเลือกตามลักษณะเฉพาะของปัญหา
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#282828', 'primaryTextColor': '#ebdbb2', 'primaryBorderColor': '#fabd2f', 'lineColor': '#83a598', 'secondaryColor': '#3c3836'}}}%%
graph LR
EA(["🧬 Evolutionary - Algorithms"])
subgraph eng["⚙️ วิศวกรรม"]
E1["Structural - Optimization - ออกแบบโครงสร้าง"]
E2["Antenna Design - ออกแบบเสาอากาศ"]
E3["Circuit Design - ออกแบบวงจร"]
end
subgraph ml["🤖 Machine Learning"]
M1["Hyperparameter - Tuning - ปรับค่า ML"]
M2["Feature - Selection - เลือก Features"]
M3["Neural Architecture - Search (NAS)"]
end
subgraph sched["📅 การจัดการ"]
S1["Job Scheduling - จัดตารางงาน"]
S2["Vehicle Routing - วางแผนเส้นทาง"]
S3["Resource - Allocation - จัดสรรทรัพยากร"]
end
subgraph game["🎮 เกมและ AI"]
G1["Game AI - พฤติกรรมตัวละคร"]
G2["Neuroevolution - วิวัฒนา Neural Net"]
G3["Procedural Content - Generation"]
end
EA --> eng
EA --> ml
EA --> sched
EA --> game
style EA fill:#cc241d,stroke:#fb4934,color:#ebdbb2
style eng fill:#3c3836,stroke:#fabd2f,color:#ebdbb2
style ml fill:#3c3836,stroke:#83a598,color:#ebdbb2
style sched fill:#3c3836,stroke:#b8bb26,color:#ebdbb2
style game fill:#3c3836,stroke:#d3869b,color:#ebdbb2
"""
ใช้ Genetic Algorithm สำหรับ Hyperparameter Optimization ของ SVM
เปรียบเทียบกับ Grid Search แบบเดิม
การติดตั้ง: pip install scikit-learn deap numpy pandas
"""
import numpy as np
import random
from sklearn.datasets import load_breast_cancer
from sklearn.svm import SVC
from sklearn.model_selection import cross_val_score, StratifiedKFold
from sklearn.preprocessing import StandardScaler
from deap import algorithms, base, creator, tools
# ========== โหลดข้อมูล ==========
data = load_breast_cancer()
X, y = data.data, data.target
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
print(f"📊 Dataset: Breast Cancer Wisconsin")
print(f" Samples: {X.shape[0]}, Features: {X.shape[1]}")
print(f" Classes: Malignant={sum(y==0)}, Benign={sum(y==1)} - ")
# ========== กำหนด Hyperparameter Space ==========
# [C, gamma] สำหรับ SVM RBF Kernel
# C : ใช้ log scale [10^-3, 10^3]
# gamma: ใช้ log scale [10^-4, 10^1]
PARAM_RANGES = {
'C_log': (-3.0, 3.0), # log10(C)
'gamma_log': (-4.0, 1.0), # log10(gamma)
}
cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
# ========== Fitness Function ==========
def evaluate_svm(individual):
"""
ประเมิน SVM ด้วย Cross-Validation
Returns:
(cv_accuracy,) — DEAP ต้องการ tuple
"""
C_log, gamma_log = individual
C = 10 ** C_log
gamma = 10 ** gamma_log
clf = SVC(C=C, gamma=gamma, kernel='rbf', random_state=42)
scores = cross_val_score(clf, X_scaled, y, cv=cv,
scoring='accuracy', n_jobs=-1)
return (scores.mean(),)
# ========== ตั้งค่า GA ==========
creator.create("FitnessMaxSVM", base.Fitness, weights=(1.0,))
creator.create("IndividualSVM", list, fitness=creator.FitnessMaxSVM)
toolbox = base.Toolbox()
def random_param(low, high):
return random.uniform(low, high)
toolbox.register("C_log", random_param,
*PARAM_RANGES['C_log'])
toolbox.register("gamma_log", random_param,
*PARAM_RANGES['gamma_log'])
toolbox.register("individual", tools.initCycle, creator.IndividualSVM,
[toolbox.C_log, toolbox.gamma_log], n=1)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("evaluate", evaluate_svm)
toolbox.register("mate", tools.cxBlend, alpha=0.5) # Blend Crossover
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=0.5, indpb=0.5)
toolbox.register("select", tools.selTournament, tournsize=3)
# ========== Boundary Constraint ==========
def check_bounds(individual):
"""ตรวจสอบว่า parameters อยู่ในขอบเขตที่กำหนด"""
ranges = list(PARAM_RANGES.values())
for i, (low, high) in enumerate(ranges):
individual[i] = max(low, min(high, individual[i]))
return individual
toolbox.decorate("mate", tools.DeltaPenalty(
lambda ind: check_bounds(ind) == ind, 0.0))
toolbox.decorate("mutate", tools.DeltaPenalty(
lambda ind: check_bounds(ind) == ind, 0.0))
# ========== รัน GA Hyperparameter Search ==========
def run_ga_hpo(n_gen=20, pop_size=30):
random.seed(42)
np.random.seed(42)
population = toolbox.population(n=pop_size)
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values[0])
stats.register("max", np.max)
stats.register("avg", np.mean)
print("🔍 เริ่ม Genetic Algorithm Hyperparameter Search...")
final_pop, log = algorithms.eaSimple(
population, toolbox,
cxpb=0.7, mutpb=0.3, ngen=n_gen,
stats=stats, halloffame=hof, verbose=True
)
return hof[0], log
# ========== ตัวอย่างการใช้งาน ==========
if __name__ == "__main__":
best_params, log = run_ga_hpo(n_gen=20, pop_size=30)
best_C = 10 ** best_params[0]
best_gamma = 10 ** best_params[1]
best_score = best_params.fitness.values[0]
print(f" - {'='*50}")
print(f"✅ ผลลัพธ์ GA Hyperparameter Optimization")
print(f"{'='*50}")
print(f" Best C : {best_C:.4f} (log={best_params[0]:.3f})")
print(f" Best gamma : {best_gamma:.6f} (log={best_params[1]:.3f})")
print(f" CV Accuracy: {best_score*100:.2f}%")
# ทดสอบกับ default parameters เพื่อเปรียบเทียบ
clf_default = SVC(kernel='rbf', random_state=42)
default_scores = cross_val_score(
clf_default, X_scaled, y, cv=cv, scoring='accuracy')
print(f" - Default SVC Accuracy: {default_scores.mean()*100:.2f}%")
print(f" การปรับปรุง: +{(best_score - default_scores.mean())*100:.2f}%")
| พารามิเตอร์ | ค่าที่แนะนำ | ผลเมื่อมากเกิน | ผลเมื่อน้อยเกิน |
|---|---|---|---|
| Population Size | 50-200 | ช้า, computation สูง | Diversity ต่ำ, Premature convergence |
| Crossover Rate (pc) | 0.7-0.9 | สูญเสียข้อมูลดีๆ | วิวัฒนาการช้า |
| Mutation Rate (pm) | 1/L – 0.1 | Search แบบ Random | ติด Local optima |
| Tournament Size | 2-5 | Selection pressure สูง | Weak selection |
| Generations | 100-1000 | Overcompute | ไม่ converge |
Premature Convergence (หยุดก่อนเวลา):
Slow Convergence (ช้าเกินไป):
Schema Theorem (ทฤษฎีโครงร่าง):
Holland เสนอว่า GA ทำงานด้วยการประมวลผล Schema ที่ดีแบบขนานโดยปริยาย:
โดยที่:
Evolutionary Algorithms เป็นกลุ่มอัลกอริทึมที่ทรงพลังและยืดหยุ่นสำหรับการแก้ปัญหาการหาค่าเหมาะสม (Optimization) ที่ซับซ้อน โดยอาศัยแรงบันดาลใจจากธรรมชาติ
ประเด็นสำคัญที่ควรจำ:
การเลือกใช้ Algorithm:
ปัญหาของคุณ → EA ที่แนะนำ
─────────────────────────────────────────
Discrete (0/1) → Genetic Algorithm (DEAP)
Continuous, smooth → CMA-ES หรือ PSO
Graph/Path/Route → ACO
สูตรคณิตศาสตร์ → Genetic Programming
Hyperparameter tuning → GA หรือ CMA-ES
Multi-objective → NSGA-II (DEAP)
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.
Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press.
Kennedy, J. & Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN'95, 4, 1942-1948.
Dorigo, M. & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog.
Hansen, N. (2006). The CMA Evolution Strategy: A Comparing Review. Towards a New Evolutionary Computation, 75-102.
Wolpert, D.H. & Macready, W.G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67-82.
Fortin, F.A., et al. (2012). DEAP: Evolutionary Algorithms Made Easy. Journal of Machine Learning Research, 13, 2171-2175. https://deap.readthedocs.io
Ahmad, F. (2021). PyGAD: An Intuitive Genetic Algorithm Python Library. https://pygad.readthedocs.io