Download presentation
Presentation is loading. Please wait.
1
Chip-based Computing + UMDA
October 4, 2002 Cho, Dong-Yeon
2
© 2002 SNU CSE Biointelligence Lab
Introduction Chip-base Computing Efficient but expensive It is impossible to search all solutions exhaustively. Evolutionary computation is necessary. UMDA (Univariate Marginal Distribution Algorithm) Ex) 해가 (T, F, F, T) 인 경우 x1 x2 x3 x4 T 0.5 F x1 x2 x3 x4 0.90 0.15 0.06 0.91 0.10 0.85 0.94 0.09 © 2002 SNU CSE Biointelligence Lab
3
DNA-Chip Based Computing
Only 4 Sequences ST, ST, SF, SF Representation 한 spot에 하나의 답을 표현하는 것이 아니라, 하나의 변수만을 표현 A1 A2 A3 AN x1 ST SF ST SF x2 ST ST SF SF xd ST SF ST SF © 2002 SNU CSE Biointelligence Lab
4
Solving 3-SAT Problem (1/2)
Fitness 주어진 clause 중 참이 된 clause의 개수 Fitness Evaluation 각 clause를 DNA로 표현하고 해당 spot에 주입하여 반응 여부를 검사 Ex) (x1 x3 x4) (ST, SF, ST) x1 SF SF SF SF ST ST ST ST x3 SF SF ST ST SF SF ST ST x4 SF ST SF ST SF ST SF ST © 2002 SNU CSE Biointelligence Lab
5
Solving 3-SAT Problem (2/2)
Update the probability A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 f 3 2 1 x1 T F x2 … © 2002 SNU CSE Biointelligence Lab
6
Indicator-Based Computing
Representation T: Acid solution F: Basic solution Fitness Evaluation Ex) BTB, (x1 x3 x4) (A, B, A) x1 B B B B A A A A x3 B B A A B B A A x4 B A B A B A B A © 2002 SNU CSE Biointelligence Lab
Similar presentations
