Chip-based Computing + UMDA October 4, 2002 Cho, Dong-Yeon
© 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
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
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
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
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