Thursday, March 03, 2005

ทดลองใช้ JGAP

อ่านเจอมานานแล้ว พึ่งได้ฤกษ์ทดลองใช้
JGAP เป็น genetic algorithms component

ไปได้ยินโจทย์่ว่า
เดิมในฐานข้อมูลลูกค้า อนุญาติให้ลูกค้าเลือก bank
ได้มากกว่า 1 bank ปัจจุบันต้องการเปลี่ยนให้ลูกค้า
ใช้ได้เพียง bank เดียวเท่านั้น
ปัจจุบันมีลูกค้าประมาณ 400000 ราย
มีจำนวน bank อยู่ 6 bank
ต้องการให้ computer ทำการเลือกธนาคารให้ลูกค้า
โดยให้แต่ละธนาคารได้จำนวนลูกค้าไปเท่าๆกัน

หลังจากได้ยินโจทย์ก็เกิด idea อยากลองใช้ JGAP solve

Step 1.
เริ่มแรกสุดที่ต้องทำการก็ออกแบบ Chromosome ว่า
จะประกอบด้วย Gene อะไรบ้าง
ลองกำหนดให้ Gene หนึ่งๆ คือ รูปแบบการเลือกธนาคาร

bank-> A B C D E F
รูปแบบที่ 1 1 0 0 0 0 0
รูปแบบที่ 2 0 1 0 0 0 0
....
รูปแบบที่ 64 1 1 1 1 1 1

ดังนั้นใน 1 chromosome จะมี gene ยังสิ้น 64 gene
จากนั้นก็เขียนโปรแกรมให้อ่านข้อมูล Raw Data
ทำการนับจำนวนคน โดย group ตาม pattern
ตัวอย่างการนับที่ได้
010011=>6370 (มีคนที่เลือกธนาคาร B, E, F ทั้งหมด 6370 คน)
ค่า 6370 จะเป็น constrain ของ Gene นั้น
ที่จะสามารถ distribute จำนวนคนไปยัง bank B หรือ E หรือ F
รวมแล้วไม่เกิน 6370 คน

ข้อมูลใน gene 1 gene ประกอบด้วย
  • constrain (ข้อมูลนี้ fix ไ่ม่เปลี่ยนไปในแต่ละรุ่น)
    • pattern การเลือก bank
    • จำนวนคนทั้งหมดที่เลือก bank ตาม pattern นี้
  • data (ข้อมูลนี้จะเปลี่ยนไปเรื่อยๆ เมื่อ evolution ไปยังรุ่นต่อไป)
    • ข้อมูลจำนวนคนที่แต่ละ bank ได้รับ
Step 2.
implement random method ของ Gene
ในตอนเริ่มต้น chromosome แต่ละ chromosome
จะถูกสร้างโดยการ random ขึ้นมา
ดังนั้นต้อง implement method นี้ให้ gene แต่ละ gene
ทำง่ายๆโดยใช้วิธี random ไปเลยว่าแต่ละธนาคารจะได้รับแจกคนไปเท่าไร

Step 3.
implement Mutation mehod ของ Gene
ทำง่ายๆโดย สุ่มโอนคนระหว่าง ธนาคารภายใน Gene นั้นๆ

Step 4.
ออกแบบ Fitness Fuction โดยถ้า chromosome ไหนได้แต้มสูง
chromosome นั้นก็มีโอกาสอยู่รอดสืบลูกสืบหลานได้
ทำง่ายๆ โดย จำนวนคนที่แต่ละธนาคารได้ ต้องไกล้เคียงกับ
400000/6 (จำนวนคนทั้งหมด/จำนวนธนาคาร)
ยิ่ง chromosome ไหนเข้าไกล้ค่าอุดมคติก็ยิ่งได้ค่าสูง

ในการ Run
สิ่งที่ต้องกำหนดก็คือ จำนวน Population ที่ใช้
จำนวนครั้งของการ evolution ที่เกิด
เลือกใช้ Population -> 500
evolution -> 10 รุ่น
ได้ผลลัพท์ดังนี้

ธนาคาร A ได้คนไปทั้งสิ้น 64162,
ธนาคาร B ได้คนไปทั้งสิ้น 65580,
ธนาคาร C ได้คนไปทั้งสิ้น 66109,
ธนาคาร D ได้คนไปทั้งสิ้น 63307,
ธนาคาร E ได้คนไปทั้งสิ้น 66026,
ธนาคาร F ได้คนไปทั้งสิ้น 68684,

เวลาในการ run = 7370 ms

ตัวอย่าง ผลลัพท์การ distribute
pattern จำนวนรวม A B C D E F
-------------------------------------------------------
111010=>6311 1337,1116,1913,0,1945,0,
001100=>6393 0,0,1161,5232,0,0,
010000=>6125 0,6125,0,0,0,0,
100100=>6422 1396,0,0,5026,0,0,
000011=>6398 0,0,0,0,82,6316,



สรุป
ผลลัพท์ที่ได้ยังไ่ม่น่าพอใจนัก
คงจะเป็นผลจากการออกแบบ fitness function ,
mutation method
ที่ยังไม่ค่อยดีนัก

ทดลองเปลี่ยนค่า จำนวน evolution
พบความประหลาดใจว่า จำนวนรุ่นยิ่งสูง
ผลลัพท์ยิ่งผิดผลาดมากขึ้น
สงสัยเราออกแบบ fitness function ผิดแน่ๆเลย

ไว้ถ้ามีโอกาสได้ data จริง ก็จะลอง
run ดูกับ data จริงดูว่าจะได้ผลลัพท์เป็นอย่างไร
(คิดว่ารูปแบบการเลือกธนาคารใน data จริง
จะมีลักษณะเฉพาะมากกว่า data test ที่เกิด
จากการ random)

Related link from Roti

2 comments:

bact' said...

เจ๋งครับ

Anonymous said...

ปัญหานี้ไม่น่าเหมาะที่จะใช้ GA แก้ครับ ใช้วิธีอื่นแก้ได้ดีกว่ามาก และการันตีผลลัพธ์ได้ครับ แต่ขอชมเชยอย่างยิ่งที่เป็นคนใฝ่รู้ เรียนรู้สิ่งใหม่ และกล้าคิดกล้าทำลงมือจริง