Bayesian Networks merupakan salah satu metode pemodelan probabilitas pada Probabilistic Graphical Models. Bayesian Networks terdiri dari nodes yang merepresentasikan variabel pada masalah yang dikaji dan edges yang merepresentasikan relasi dependensi antar node. Pada masalah yang sederhana, struktur Bayesian Networks biasanya ditentukan oleh ahli di bidang masalah tersebut atau berasal dari intuisi alami manusia. Perancangan struktur Bayesian Networks secara manual ini akan sulit dilakukan apabila kasus yang dikaji merupakan kasus yang kompleks yang memiliki sangat banyak node dan sangat banyak kemungkinan edges yang menghubungkannya. Pada penilitian ini, dilakukan pengujian dan analisa terhadap proses pencarian struktur Bayesian Networks menggunakan algoritma Novel Modified Binary Differential Evolution. Novel Modified Binary Differential Evolution merupakan algoritma optimasi permasalahan diskrit dengan representasi solusi berbentuk biner yang merupakan pengembangan dari algoritma Differential Evolution. Hasil pengujian terhadap data Alarm, Asia, Carpo, Insurance, dan Water masing-masing diperoleh skor BDeu sebesar -1973.77, -243.68, -2450.54, -2024.17, dan -1621.90.