Python

กำลังศึกษาขั้นตอนการทำงานของ Genetic Algorithm ว่ามีขึ้นตอนและการทำงานอย่างไรอยู่ในตอนนี้

เลยลองหา Case Study มาศึกษาเพื่อให้เข้าใจ และเห็นการทำงานของ GA ได้ดียิ่งขึ้น สำหรับกรณีศึกษาที่ง่ายที่สุดเท่าที่จะนึกออกสำหรับปัญหาประเภท Combinatorial Optimization Problem ก็คงหนีไม่พ้น Traveling Salesman Problem (TSP)

ทดลองเขียนโปรแกรมเล็กขึ้นมา เพื่อทดลองและศึกษาขึ้นตอนการทำงานของ GA ก่อนสำหรับรายละเอียดของการทดลงคงมีดังนี้
ี้

1. Chromosome Encoding ใช้แบบ Permutation Encoding

2. Selection ใช้แบบ Tournament คือสุ่ม Chromosome ขึ้นมา 10 ตัวเลือกเอา 2 ตัวที่ดีที่สุดมาดำเนินการต่อไป

3. Crossover ใช้การ Crossover ในแบบที่กระทำกับข้อมูลที่อยู่ในรูปแบบ Permutation Encoding

4. Population Size ตั้งขนาดไว้ที่ 50 ประชากรต่อรุ่น

5. Stop Condition เมื่อค่าคำตอบที่เป็นค่าที่ดีที่สุดของแต่ละรุ่นไม่มีการเปลี่ยนแปลง (มีลักษณะเร่ิมลู่เข้าสู่คำตอบ) ติดต่อกัน 100 Generations

6. การสร้างเมืองใช้การสุ่มจุดขึ้นตามจำนวนเมืองที่เป็น Input ของโปรแกรม และจุดตั้งต้นสำหรับการเดินทางจะเร่ิมจากจุดที่ 1 เสนอ การเดินทางจะคิดขาไปอย่างเดียว ดั้งนั้นเส้นทางจะไม่เป็นวงรอบ

7. พัฒนาด้วย Python 2.4

8. ต้องการ Module wxPython, Numeric

Source Code : Genetic Algorithm for TSP

Basic Genetic Algorithm

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

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

สามารถแจงรายระเอียดได้ดังนี้

- Chromosome Encoding
คือ ขั้นตอนสำหรับแปลงทางเลือกสำหรับการแก้ปัญหาที่เป็นไปได้ให้อยู่ในรูปแบบของ Chromosome
ในการแปลงวิธีการสำหรับแก้ปัญหาที่เป็นไปได้ ให้อยู่ในรูปแบบของ Chromosome นั้นสามารถที่จะทำได้ในหลายรูปแบบซึ่งแล้วแต่ความเหมาะสมของแต่ละปัญหา

- Initial Population
คือ การสุ่มเลือกเพื่อสร้างประชากรต้นแบบขึ้นมาเพื่อใช้เป็นจุดเริ่มต้นของขั้นตอนการวิวัฒนาการ
ขั้นตอนนี้จะเป็นขึ้นตอนแรกที่เกิดขึ้นก่อนที่จะเร่ิมเข้ากระบวนการของ Genetic Algorithm โดยประชากรกลุ่มแรก หรือประชาการต้นกำเนิด จะเกิดจากการสุ่มเลือกขึ้นมาจาก กลุ่มของประชากรทั้งหมดที่มีอยู่ โดยในการสุ่มเลือกจะทำการสุ่มตามจำนวนของประชากรที่ได้กำหนดไว้เป็น Parameter ของ Algorithm

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

- Genetic Operator
คือ การคำเนินการต่างๆ ตามขั้นตอนของ Genetic Algorithm เพื่อให้การเกิดวิวัฒนาการไปสู่คำตอบที่ดีขึ้น ซึ่งได้แก่ Selection, Crossover และ Mutation

- Parameter
คือ ปัจจัยที่ส่งผลต่อการทำงานของ Genetic Algorithm เช่น ขนาดของประชาการ, ความน่าจะเป็นของการ Crossover หรือ ความน่าจะเป็นของการ Mutation

1. Crossover Probability คือ ความน่าจะเป็นของการเกิด Crossover ซึ่งมีค่าอยู่ในช่วง 0 - 100 โดยทั่วไปค่าความเหมาะสมของความน่าจะเป็นในการเกิด Crossover จะอยู่ที่ 60% - 95% และในกรณีที่ไม่เกิดการ Crossover เกิดขึ้นจะเป็นการทำสำเนา (Copy) รูปแบบของพันธุกรรมจาก Parent ไปสู่ Offspring เลย ยกตัวอย่าง การทำ Crossover เช่น เรากำหนดให้ Crossover Probability มีค่าเป็น 85% ถ้าเราทำการสุ่มเลือกตัวเลขขึ้นมาเพื่อเปรียบเทียบกับค่า Crossover Probability ได้เท่ากับ 20 นั่นคืออยู่ในช่วงที่ <= 85 ในกรณีจะยอมให้เกิดการ Crossover เกิดขึ้น

2. Mutation Probability คือ ความน่าจะเป็นของการเกิด Mutation จะมีค่าอยู่ในช่วง 0 - 100 ส่วนใหญ่ค่าความน่าจะเป็นของการเกิด Mutation จะถูกกำหนดไว้ให้อยู่ในช่วง 0% - 1% ต่อตำเหน่งของ Chromosome ในกรณีที่ไม่มีการ Mutation นั่นหมายความว่ามีเพียงการ Crossover เกิดขึ้นเพียงอย่างเดียว แต่ถ้าหากว่า เกิดการ Mutation 100% จะทำให้ทุกตำเหน่งใน Chromosome มีการเปลี่ยนแปลงทั้งหมด ซึ่งสำหรับใน Genetic Algorithm นั้นอาจเกิดกรณีนี้ขึ้นได้ แต่ไม่บ่อยนัก ไม่เช่นนั้นการค้นหาจะเปลี่ยนจาก Genetic Algorithm การเป็น Random Search

3. Population Size หรือ จำนวนของประชากรในแต่ละรุ่น ถ้ามีจำนวนมากเกิดไปจะทำให้ต้องเสียเวลาในการประมวลผลมากและทำงานได้ช้าลง หรือ หากน้อยเกินไปก็จะทำให้การค้นหานั้นสามารถที่จะลู่เข้าสู่คำตอบที่เป็น Global Minimum ได้ช้าเกินไป

แผนผังลำดับของขั้นตอนการทำงาน

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

ข้อมูลศึกษาเพ่ิมเติมจาก :
http://cs.felk.cvut.cz/~xobitko/ga/

วันนี้ทดลองเขียนโปรแกรมเพื่อเปิดไฟล์ขึ้นมาเพื่ออ่านดูเล่นๆ
แต่ปรากฏว่ามันมีปัญหาเรื่องการอ่านไฟล์ที่เป็นภาษาไทย

สำหรับทางแก้ไขให้เปิดไฟล์ภาษาไทยได้ก็คงมีดังนี้

fileencoding = "utf-8"
f = open(file, 'r')
for eachline in f.readlines():
     txt = unicode(eachline, fileencoding)

บันทึกความในใจ :

นั่ง งม และ งง อยู่งาน หลังจากอยู่ๆ ก็เกิดความคิดว่าน่าจะลองใช้ Python ทำเว็ปดูบ้าง

ไม่รู้เลยว่าจะต้องเริ่มต้นจากตรงไหน พยายามงมทางอยู่นาน ลองแล้วลองอีก เรียกได้ว่าเกือบจะลองมันทุกทางเลยก็ว่าได้

เหมือนคนหน้ามืด ตาบอด พยายามค้น พยายามอ่าน พยายามศึกษาด้วยตัวเอง มั่วแบบหัวชนฝาเลยก็เอา

กว่าจะเซ็ดเครื่องผ่าน compile โปรแกรมอยู่เป็นสิบๆ รอบ ทำอยู่ทั้งคืน ไม่ได้หลับไม่ได้นอน ก็เซ็ตไม่ผ่าน หว่ะ ท้อใจ

ลองแล้วลองอีก สุดท้ายมันก็ฟลุ๊ค ได้ซักทางนั่นแหล่ะหน่ะ

เซ๊ตเครื่องได้แล้ว ... แล้วจะใช้ Python เขียนเว็ปมันต้องทำยังไงว่า ???

ลองอ่านๆ ดู อ้อมันมี Framework ให้ใช้ โอเค หลับตาเลือกมาตัวหนึ่งละกัน

ตัดสินใจเลือก Django มาแล้วยังไงต่อดี เพราะเกิดมายังไม่เคย ยังไม่เคยเขียนเว็ปโดยใช้ Framwork เลย

และก็ยังไม่เคยรู้เลยว่าการทำงานด้วย Web Framwork มันต้องทำยังไง มันดียังไง ???

ทางเดียวก็คืออ่าน อ่าน และอ่าน แต่คงต้องขอบ่นหน่อยว่า Document ของเข้า Django นี่มันห่วยมาก ถึงขึ้นห่วยแตกเลย

ต้องอ่านแล้วอ่านอีก อ่านอยู่นานกว่าจะเข้าใจ(และก็ยังเข้าใจแบบครึ่งๆ กลางๆ ด้วย)

ผ่านไป 2 อาทิตย์กับความพยายามที่เกือบจะกลายเป็นความท้อ กว่าจะได้ Web Application เล็กๆ ให้ทำเป็นตัวอย่าง ที่ให้พอได้ชื่นใจว่าทำได้แล้ว

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

แต่เย็นนี้ขอไปกินหมูกระทะก่อน เหนื่อยมากๆ เลยเน๊อะ น้องนำ้เน๊อะ

เฮ้อ... เอาหล่ะหลังจากติดตั้ง Module Numpy เรียบร้อยแล้ว และก่อนที่จะเขียนถึงวิธีการติดตั้ง Mudule Pypar นั้นขอบันทึกความยากลำบากสำหรับการติดตั้งเจ้า Module ของ Python ที่ใช้สำหรับเขียนโปรแกรมแบบ Parallel นี้ไว้ซักหน่อยก็แล้วกัน

เร่ิมต้นจากความไม่รู้ ส่ิงเดี่ยวที่รู้ในตอนนี้ก็คือ ว่าเราใช้ Python เขียนโปรแกรม เอ... แล้วถ้าต้องการเขียนโปรแกรมให้มันสามารถ run แบบ Parallel หล่ะ เจ้า Python นั้นมันจะทำได้ไม้หว่า

ดูไป ดูมา อ่านไป อ่านมา สรุปว่าอ้อ โดยความสามารถพื้นฐานนั้นมันทำไม่ได้ แต่มันพอมีทางทำได้อยู่ โดยการติดตั้ง Module เพิ่มเข้าไป ซึ่ง Module เหล่านี้มันก็จะมีพวก API ต่างๆ ที่ใช้สำหรับช่วยให้สามารถสั่งงาน หรือเขียนโปรแกรมแบบ Parallel ได้โดยจะทำงานร่วมกับโปรแกรม MPI (Message Passing Interface)

เออ แล้วมันมี Module อะไรบ้างหว่าที่ช่วยให้สามารถทำงานอย่างที่ว่าได้

ลองเข้าไปอ่านในนี้ดู : http://wiki.python.org/moin/ParallelProcessing

โอ้ ... ทำไมมันมีหลายตัวจะเลยหง่ะ

แล้วจะใช้ตัวไหนดีหล่ะ อย่างนี้ คงต้องลองผิดลองถูก กันดูซักตั้ง เริ่มสุ่มเลือกมาทีละตัวเลย
ผลก็คือ บางตัวก็ Compile ไม่ผ่าน ลองแล้ว ลองอีก ทำทุกทางแล้ว ก็ยัง Compile ไม่ผ่านซักที ลองอ่านในคู่มือของมันดู เอ.. ทำมันเขียนเหมือนหลับตาลงยังลงได้เลย แล้วทำไมเราลงไม่ได้ซักทีวะ ลองไม่รู้กี่รอบแล้ว ทำมันก็ทุกทางแล้ว สุดท้ายก็ไม่ได้

เอาใหม่ ไอ้ตัวนี้ไม่ได้ก็เปลี่ยนตัวใหม่ มั่วมันไปเรื่อยๆ หลายตัวผ่านไปก็ยังไม่ได้ซักที ลงอีกหรอบเดียวกันหมดคือ Compile ไม่ผ่านซักที

และแล้วก็มาหยุดที่เข้าตัวนี้ ScientificPython ติดตั้งได้ซะที แต่มันก็ซับซ้อนอยู่ซักหน่อย ต้องอ่าน Manaul หรือ Readme ที่มันไว้มาด้วยดี ต้องอ่านให้ระเอียด ถึงจะเข้าใจว่ามันต้องติดตั้งยัง แล้วก็ต้องแก้ปัญหาอีกพอสมควรเนื่องจากใน Mac OS X ในระหว่าง Compile มันจะอ่าน Path ผิดไปต้องทำการแก้ Paht ให้ถูกต้อง แต่ถ้าเป็นใน Linux จะไม่มีปัญหาอะไร

หลังจากติดตั้ง ScientificPython เรียบร้อยแล้ว ดีใจอยู่หลายวัน ตั้งหน้าตั้งตา รีบหา manual ของมันมาอ่าน ๆ และก็อ่าน อยู่หลายวันเลยกว่าจะรู้เรื่อง แต่พอทำงานจริงกลับเจอปัญหาหลายอย่างเลย รู้สึกว่ามันจะทำงานได้ไม่ค่อยสมบรูณ์นัก และรู้สึกว่ามันจะขาด API บางอย่างที่จำเป็นไปด้วย (สรุปปัญหาของมันก็คือ มันมี API สำหรับงานทางด้าน Scientific มากมาย แต่สำหรับ API ทางด้านเกี่ยวกับ MPI มันกลับมีไม่ครบ)

รู้สึกถอดใจอยู่พักใหญ่เลย แต่ยังไงก็ต้องทำงานต่อ คงต้องเร่ิมกันใหม่ มั่วกันต่อ

คราวนี้ลอง Download เจ้า Pypar มาลองดู ตอนแรกไม่ค่อยประทับใจเท่าไหร่นัก เนื่องจากเข้าไปที่หน้าเว็บ ปรากฏว่ามี Information ที่ให้ไว้น้อยมาก ไม่มี Manaul ไม่มี Document มีแต่ตัวอย่างง่ายๆ แปะไว้ให้ดูที่หน้าเว็ปอยู่ตัวอย่างเดียว

แต่มาถึงขนาดนี้ไม่ลองก็ไม่ได้ ก็เลยกลั้นใน Download มันมาทดลองติดตั้งดูหน่อย
ผลปรากฏว่า ติดตั้งง่ายกว่าที่คิดเยอะเลย ติดตั้งได้เลย โดยที่ไม่ต้องเสียเวลามานั่งอ่าน Readme ด้วยซ้ำ

คราวนี้มาถึงการทำลองทำงานจริง โดยการทดลองเขียนโปรแกรมแบบ Parallel ปรากฏว่าเจ้า Pypar มันไม่มี Manual หรือว่า Document ให้มาเลยลองมีแต่ Source Code ของโปรแกรมตัวอย่างติดมาให้อยู่ 6 - 7 ตัวอย่างเท่านั้น

ดังนั้นการศึกษาให้รู้เรื่องคงมีทางเดียวคือ นั่งไล่ Source Code ของตัวอย่างที่ให้มาเท่านั้น

โอเค สรุปเลยก็แล้วกันว่าตกลงใช้ Pypar นี่แหล่ะ ติดตั้งง่าย ใช้งานดี

เอาหล่ะบนมาพอแล้วคงต้องบันทึกวิธีการติดตั้งเอาไว้บ้างแล้ว
เร่ิมจาการไป Download Souce Code ของ Pypar ได้ที่

Download : http://datamining.anu.edu.au/~ole/pypar/pypar_1_9_2.tgz

จากนั้นก็ทำการแตกไฟล์ที่ Download มาและเข้าไปยัง Directory ที่ได้จากการแตกไฟล์
และทำการติดตั้งด้วยคำสั่งต่อไปนี้

# python setup.py build
# python setup.py install

หลังจากทำการติดตั้งโปรแกรม LAM/MPI เรียบร้อยแล้ว และเพื่อให้สามารถทำการติดตั้ง Module ของ Python ที่ช่วยให้สามารถทำการเขียนโปรแกรมแบบ Parallel ได้ก็คือเจ้า Module ที่ชื่อว่า Pypar นั้น

มันมีความจำเป็นจะต้องทำการติดตั้ง Module ที่ชื่อว่า Numpy เข้าไปก่อนจึงจะสามารถทำการติดตั้ง Mudule Pypar เข้าไปได้

สำหรับการการติดตั้ง Mudule Numpy นั้นไม่ยากเย็นอะไรสามารถเข้าไปโหลดได้ที่

Download : http://numpy.scipy.org

ทำการแตกไฟล์แล้วเข้าไปภายใน Directory ที่ได้หลังจากการแตกไฟล์
แล้วจึงทำการติดตั้ง Module Numpy โดย

# python setup.py build
# python setup.py install

เมื่อทำการติดตั้งเรียบร้อยแล้วสามารถทำการทดสอบผลของการติดตั้งได้โดย

# python
>>import Numeric
>>

ถ้าไม่ฟ้องหรือแสดง error message ใดๆ แสดงว่าใช้ได้แล้ว