มารู้จัก Genetic Algorithm พื้นฐานกัน มันกว่าที่คิด

Genetic Algorithm 

           ขั้นตอนวิธีเชิงพันธุกรรม (Genetic Algorithm – GA) เป็นเทคนิคทางปัญญาประดิษฐ์ (AI : artificial intelligence) อย่างหนึ่งที่ใช้ในการค้นหา การเพิ่มประสิทธิภาพ และการเรียนรู้ (Search, Optimization, and Learning) ด้วยการเลียนแบบทฤษฎีการวิวัฒนาการทางธรรมชาติ โดยขั้นตอนวิธีเชิงพันธุกรรมมีจุดเด่นในด้านความทนทานต่อความผิดพลาดในการค้นหาคำตอบจากแหล่งข้อมูลที่มีความซับซ้อนและยากที่จะสร้างแบบจำลองด้วยสมการคณิตศาสตร์ เนื่องจากเป็นกระบวนการค้นหาที่ไม่มีความเฉพาะเจาะจงกับแบบจำลองหรือลักษณะเฉพาะของข้อมูลแบบใดแบบหนึ่ง ด้วยเหตุนี้ขั้นตอนวิธีเชิงพันธุกรรมจึงถูกนำมาประยุกต์ใช้ในการแก้ปัญหาได้หลากหลายรูปแบบ
     - ตั้งแต่การจัดตารางเวลา (Timetable Scheduling)
     - การออกแบบระบบควบคุมอัตโนมัติ (Control System Design)
     - การออกแบบเพื่อเพิ่มประสิทธิภาพของระบบท่อส่งก๊าซ (Gas Pipeline Optimization)
     - การพัฒนาระบบปัญญาประดิษฐ์ (AI : artificial intelligence) ที่สามารถเรียนรู้จากสภาพแวดล้อมได้ (Genetic Based Machine Learning)
     เป็นต้น
    โดยหลักการของขั้นตอนวิธีเชิงพันธุกรรม เป็นการเลียนแบบกระบวนการวิวัฒนาการตามธรรมชาติ เพื่อพัฒนาหรือทำการ

“วิวัฒนาการ” 

คำตอบที่ดีที่สุดในการแก้ปัญหา

ที่มา : https://kapitaennem0.wordpress.com/2013/07/17/genetic-algorithm/

(ผู้เขียนบล๊อกนี้อธิบายได้ดี ผมจึงนำมานำเสนอต่อ)

Genetic Algorithm มีอะไรบ้าง

สำหรับองค์ประกอบหลักๆ ของ Genetic Algorithm มีดังนี้

1. Chromosome Encoding
2. Initial Population
3. Fitness Function
4. Genetic Operator -> Selection, Crossover, Mutation
5. Replacement

1. Chromosome Encoding

เป็นขั้นตอนในการแปลงปัญหาให้เป็น Chromosome หรือพูดง่ายๆคือ รูปแบบหรือรูปร่างของข้อมูลของปัญหานั้นๆ
เช่น ปัญหา Binary Encoding จะมีลักษณะของ Chromosome เป็นดังนี้

1001 1011

นิยามให้มันมี 0 หรือ 1 และมียีนในแต่ละ  Chromosome ทั้งหมด 8 ตัว

2. Initial Population

คือการ สร้างประชากรขึ้นมาโดยการสุ่มสร้างหรือสุ่มเลือกขึ้นมา และการสร้างจำนวนประชากร(จำนวน Chromosome) จะเป็น Parameter ของ Algorithm
เช่น เราจะสร้างประชากรขึ้นมา 4 Chromosome โดยการสุ่มเลข 0 , 1 เข้าไปใน Chromosome

A: 0110 0100
B: 0010 1011
C: 1110 1101
D: 1101 1001

3. Fitness Function

คือสิ่งที่จะใช้ในการการประเมินค่าความเหมาะสม หรือ คะแนนของประชากรนั้นๆ เพื่อใช้ในการพิจารณาว่า โครโมโซมตัวนั้น เหมาะหรือไม่ที่จะนำมาใช้สืบทอดพันธุกรรมสำหรับสร้างโครโมโซมรุ่มใหม่หรือไม่ โดยสมการหรือวิธีการในการคิดค่า Fitness นั้นขึ้นอยู่กับปัญหานั้นๆ
เช่น ในปัญหา Binary Encoding เราจะให้ Chromosome ที่มีเลข 1 จะนับเป็น 1 คะแนน

A: 0110 0100 = 3
B: 0010 1011 = 4
C: 1110 1101 = 6
D: 1101 1001 = 5

4. Genetic Operator

จะให้พูดง่ายๆในขั้นตอนนี้คือ เป็นวิธีปรับเปลี่ยนองค์ประกอบของ Chromosome ซึ้งจะแบ่งออกเป็น 3 ส่วนได้แก่
       1 Selection
          เพื่อให้เกิดการอยู่รอดของสิ่งมีชีวิต จึงต้องทำการคัดเลือกประชากรบางส่วนเพื่อใช้ในการสืบทอดในรุ่นถัดไป ซึ้งในที่นี้คือการคัดเลือก Chromosome ที่จะใช้ในการทำขั้นตอน Genetic ในขั้นตอนถัดไป โดยวิธีการคัดเลือกนั้นก็มีมากมายหลายอย่าง เช่น
   - Roulette Wheel
   - Ranking
   - Tournament
   - Elitist
   - Steady State
   เป็นต้น
โดยปัญหา Binary Encoding นั้นเราจะใช้วิธีการคัดเลือกทั้งหมด (ง่ายดี) และสำหรับการ Crossover จะใช้ค่า Fitness ที่ดีที่สุดผสมกัน

        2 Crossover
           เป็นกระบวนการในการนำ 2 Chromosome มาผสมกันกันเพื่อให้ได้ Chromosome ใหม่ๆเกิดขึ้น
และสำหรับ ปัญหา Binary Encoding เราจะใช้วิธีที่ง่ายที่สุดคือ แบ่งครึ่ง Chromosome ระหว่าง 2 Chromosome และนำมาผสมกัน

C: 1110 1101 = 6
D: 1101 1001 = 5
B: 0010 1011 = 4
A: 0110 0100 = 3

ดังนั้น  C กับ D , A กับ B จะ Crossover กัน

C' : 1110 / 1001
D' : 1101 / 1101
B' : 0010 / 0100
A' : 0110 / 1011

       3 Mutation
          คือการทำการเปลี่ยนแปลงคุณลักษณะภายใน Chromosome ในบางตำแหน่งของรุ่นลูกเพื่อให้เกิดลักษณะใหม่ๆเกิดขึ้น เช่น จากตัวอย่าง ในตำแหน่งยีนที่ 7 สิ่งใดมีค่าเป็น 0 ให้เปลี่ยนเป็น 1 ทั้งหมด

C' : 1110 / 1011
D' : 1101 / 1111
B' : 0010 / 0110
A' : 0110 / 1011

5. Replacement
หรือการแทนที่ประชากรรุ่นเก่า ซึ้งวิธีการแทนที่ก็มีหลายหลายรูปแบบมากมาย ไม่ว่าจะเป็นการแทนที่ประชากรรุ่นเก่าทั้งหมด หรือการแทนที่ประชากรเฉพาะบางประชากรเท่านั้นโดยมีวิธีเลือกจากค่า Fitness หรือ ประชากรที่ถูกคัดเลือกจาก Selection แล้ว copy ประชากรที่ไม่ได้ถูกเลือก Selection มาเป็นรุ่นถัดไป บลาๆๆๆๆๆๆๆๆ มากมาย

จากนั้นถ้ายังได้ประชากรรุ่งนที่เรายังไม่ถูกใจ ก็ไปเริ่มกระบวนการใหม่ในขั้นตอนที่ 2 ไปเรื่อยๆ จะกว่าจะถึงจุดที่เราพอใจ แล้วแต่ว่าจุดที่เราพอใจคืออะไร หรือวัดจากอะไรแล้วแต่ความเหมาะสมของปัญหานั้นเอง

ทั้งหมดนี้คือ Genetic Algorithm ขั้นพื้นฐานเท่านั้น ซึ้งเป็น Algorithm ที่ใช้ศิลปะในการทำอีกมากมาย ซึ้งมันทำให้ผมรู้สึกสนุกนั้นเอง ... ผิดพลาดประการก็ขออภัยมา ณ ที่นี้ด้วยครับ หรือมีอะไรเพิ่มเติมก็ comment มาด้านล่างได้เลยครับ

PDO มีมานานแต่หลายคนก็ไม่ใช้ (การ PHP Connect Database แบบ PDO)

ใช้มัน(PDO)ทำไม

ก่อนอื่นการใช้ query แบบเดิมๆที่เราใช้กันจะเป็นในลักษณะนี้

<?php

$host = "localhost" ;
$username = "xxx" ; // ชื่อผู้ใช้ในการติดต่อกับฐานข้อมูล
$password = "xxx" ; // password ในการเชื่อมต่อกับฐานข้อมูล
$dbname = "xxx" ;  // ชื่อฐานข้อมูล
$c = mysql_connect($host,$username,$password); // ติดต่อฐานข้อมูล
if (!$c){
    echo "<h3>ERROR : ไม่สามารถติดต่อฐานข้อมูลได้</h3>";
    exit();
}
mysql_query("SET NAMES UTF8"); // สำหรับการติดต่อฐานข้อมูลแบบ UTF8
mysql_select_db($dbname,$c); // สำหรับเลือกชื่อฐานข้อมูลที่ต้องการติดต่อ
 ?>



ต่อมาเราจะลอง query เพื่อตรวจสอบการ login ของ user จากตาราง user

<?php

$sql = "SELECT username FROM user
WHERE username = '$_POST[username]' AND password = '$_POST[password]'";

mysql_query($sql); 

?>

ถ้าในกรณีที่เราใส่ข้อมูลใน form กรอก username ด้วยชื่อ username ของใครก็ได้แล้วตามด้วย -- (หมายความว่าเป็นการ comment ของภาษา sql) แล้วพิมพ์ password อะไรลงไปก็ได้

ดังนั้นเราจะได้รูปแบบคำสั้งดังนี้

SELECT username FROM user WHERE username = 'user01' -- AND password = XXX

 ดังนั้นเงื่อนไขจะเป็นจริงตลอด จึง login เข้าได้โดยไม่ต้องรู้ password ก็ได้

แล้วใช้ PDO ยังไงหว่า
ดังนั้นเราจึงมาเลือกวิธีการแบบ PDO กันดีกว่า โดยจะเป็นไปในลักษณะนี้
<?php

// ระบุค่า host และชื่อของ database

$dsn = 'mysql:host=localhost;dbname=XXX';

// ระบุ username และ password 

$username = 'username';
$password = 'password';

// คือการต่อเข้ากับฐานข้อมูลแบบ UTF-8

$options = array(
    PDO::MYSQL_ATTR_INIT_COMMAND => 'SET NAMES utf8',
);
$dbh = new PDO($dsn, $username, $password, $options);

?>

และเมื่อเราทำการ connect เข้ากับ database แล้ว ทีนี้เราจะมาลอง query แบบง่ายๆกันดีกว่า

<?php

// เราจะต้องทำการ prepare คำสั่ง SQL สะก่อน$sth = $dbh->prepare("SELECT username FROM user WHERE username = :username AND password = :password");

// จากนั้นทำการ execute คำสั่ง SQL พร้อมนำข้อมูลที่ต้องการ binding เข้าไปใน ? ที่เราตามที่เราต้องการ โดยที่มันจะทำหน้าที่ตัดข้อความที่ไม่พึงประสงค์ออกไปในเบื้อต้น$result = $sth->execute(               array(':username' => $_POST['username'], ':password' => $_POST['password'])               ); 

// ตรวจสอบว่า execute ผ่านหรือไม่if($result) {             // ทำการ fetch ค่าออกมาใช้งาน โดย PDO::FETCH_ASSOC คือการใช้ชื่อ colum name เป็น index ของ array            $result = $sth->fetch(PDO::FETCH_ASSOC);            print_r($result);}

?>

ปลอดภัยกว่ากันตั้งเยอะ ดังนั้นมาใช้ PDO กันเถิดครับ