215E225 TÜBİTAK 3001 PROJESİ SONUÇ RAPORU
Genetik Programlama ile Rastgele Sayı Üretimi ile İlgili Çalışmalar
GP metoduyla rastgele sayılar veya SRSÜ üreten geçmiş çalışmalar bulunmaktadır. Bu alandaki ilk çalışmalardan biri Koza’nın genetik algoritma ile elde ettiği rastgele sayı üretecidir (Koza, 1991). Bu üreteç verilen bir ardışık sayı dizisini, rastgele sayılara dönüştürmektedir. Bu nedenle çoğunlukla görülen, tekrarlanan yapıdaki SRSÜ’lerden farklıdır.
Koza, ifade ağaçlarını kullanarak rastgele sayı üretmeyi amaçlamıştır. Burada genetik algoritma, operatörlere uygulanmaktadır ve sonucunda bir fonksiyon üretilmektedir. Genetik algoritmada ağaç kodlama ve tek noktalı çaprazlama kullanılmış olup mutasyon yöntemi uygulanmamıştır. Her yeni jenerasyonda, popülasyonun %10’una seçme yöntemi, %90’ına çaprazlama yöntemi uygulanıp yeni popülasyon üretilmiştir. Uygunluk fonksiyonunda entropi hesabı yapılmıştır. Girdi olarak 1’den 16384 (214)’e kadar olan sayılar verilmiş ve sonuçta üretilen sayıların testlerden geçtiği gözlenmiştir.
Koza’nın çalışması uygunluk fonksiyonu olarak, proje çalışmamızdaki gibi, bit entropi hesabını kullanmaktadır. Yüksek entropiye sahip sonuç dizileri daha uygun olarak kabul edilmektedir. Sonuçlarında frekans ve gap testi gibi testler kullanılsa da NIST STS gibi bütün bir test uygulanmamıştır. Ayrıca, kullanılan bölme ve mod hesaplama gibi operasyonlar donanımsal olarak güçlü olmayan cihazlar için sorun teşkil edebilir.
Hernandez-Castro, Isasi, ve Seznec’in çalışması Genetik Algoritma (GA) uygunluk fonksiyonu olarak çığ etkisi (avalanche effect) ve katı çığ kriterini (strict avalanche criterion) kullanmaktadır (Hernández-Castro, Isasi ve Seznec, 2004). Bu algoritma Mersenne Twister ile başlangıç rastgele sayıları üretir ve bu sayıların rastgele seçilen bir bitini değiştirir. Sonrasında, bu değerler ve SRSÜ’den üretilen çıktı değeri arasındaki Hamming mesafesi üzerinden bir uygunluk değeri hesaplar.
Katı çığ kriterini uygunluk fonksiyonu olarak kullanan bir diğer benzer çalışma ise LAMED’dir (Peris-Lopez vd., 2009). LAMED’de de, proje çalışmamızdaki gibi donanımsal olarak güçlü olmayan cihazlar hedef olarak seçilmiştir. Ayrıca LAMED çalışmasında, RFID etiketleri için EPC standartlarına uygun bir SRSÜ’nün yanında, SRSÜ’nün donanımı da tasarlanmıştır. WISP programlanabilir bir mikrodenetleyiciye sahip olduğundan, proje çalışmamızda LAMED gibi donanım tasarımına gerek duyulmamıştır.
Jhajharia, Mishra ve Bali (Jhajharia, Mishra ve Bali, 2013) yaptıkları çalışmada genetik algoritma kullanarak daha iyi ve hızlı rastgele sayılar üretmeyi amaçlamışlardır. Başlangıç popülasyonu için programlama dilinin random() fonksiyonu kullanılarak üretilen sayılara genetik algoritma adımları uygulanmıştır. Genetik algoritmada rulet tekerleği seçimi, ring ve cut point kullanarak one point crossover ve %50 olasılık oranıyla mutasyon yöntemleri uygulanmıştır. Shannon entropi ve Ki-kare testi uygunluk fonksiyonu olarak seçilmiştir.
1) Shannon Entropi değerini hesapla : H(X) = - (p * (log2(p))) - ((1 - p) * (log2(1 - p)))
2) Ki-kare değerini hesapla: 2 = (gözlenen_H - beklenen_H)2/(beklenen_H)
3) Otokorelasyon katsayısını hesapla: φ2 (Phi-coefficient) = 2 / örnek_sayısı
Koza, ifade ağaçlarını kullanarak rastgele sayı üretmeyi amaçlamıştır. Burada genetik algoritma, operatörlere uygulanmaktadır ve sonucunda bir fonksiyon üretilmektedir. Genetik algoritmada ağaç kodlama ve tek noktalı çaprazlama kullanılmış olup mutasyon yöntemi uygulanmamıştır. Her yeni jenerasyonda, popülasyonun %10’una seçme yöntemi, %90’ına çaprazlama yöntemi uygulanıp yeni popülasyon üretilmiştir. Uygunluk fonksiyonunda entropi hesabı yapılmıştır. Girdi olarak 1’den 16384 (214)’e kadar olan sayılar verilmiş ve sonuçta üretilen sayıların testlerden geçtiği gözlenmiştir.
Koza’nın çalışması uygunluk fonksiyonu olarak, proje çalışmamızdaki gibi, bit entropi hesabını kullanmaktadır. Yüksek entropiye sahip sonuç dizileri daha uygun olarak kabul edilmektedir. Sonuçlarında frekans ve gap testi gibi testler kullanılsa da NIST STS gibi bütün bir test uygulanmamıştır. Ayrıca, kullanılan bölme ve mod hesaplama gibi operasyonlar donanımsal olarak güçlü olmayan cihazlar için sorun teşkil edebilir.
Hernandez-Castro, Isasi, ve Seznec’in çalışması Genetik Algoritma (GA) uygunluk fonksiyonu olarak çığ etkisi (avalanche effect) ve katı çığ kriterini (strict avalanche criterion) kullanmaktadır (Hernández-Castro, Isasi ve Seznec, 2004). Bu algoritma Mersenne Twister ile başlangıç rastgele sayıları üretir ve bu sayıların rastgele seçilen bir bitini değiştirir. Sonrasında, bu değerler ve SRSÜ’den üretilen çıktı değeri arasındaki Hamming mesafesi üzerinden bir uygunluk değeri hesaplar.
Katı çığ kriterini uygunluk fonksiyonu olarak kullanan bir diğer benzer çalışma ise LAMED’dir (Peris-Lopez vd., 2009). LAMED’de de, proje çalışmamızdaki gibi donanımsal olarak güçlü olmayan cihazlar hedef olarak seçilmiştir. Ayrıca LAMED çalışmasında, RFID etiketleri için EPC standartlarına uygun bir SRSÜ’nün yanında, SRSÜ’nün donanımı da tasarlanmıştır. WISP programlanabilir bir mikrodenetleyiciye sahip olduğundan, proje çalışmamızda LAMED gibi donanım tasarımına gerek duyulmamıştır.
Jhajharia, Mishra ve Bali (Jhajharia, Mishra ve Bali, 2013) yaptıkları çalışmada genetik algoritma kullanarak daha iyi ve hızlı rastgele sayılar üretmeyi amaçlamışlardır. Başlangıç popülasyonu için programlama dilinin random() fonksiyonu kullanılarak üretilen sayılara genetik algoritma adımları uygulanmıştır. Genetik algoritmada rulet tekerleği seçimi, ring ve cut point kullanarak one point crossover ve %50 olasılık oranıyla mutasyon yöntemleri uygulanmıştır. Shannon entropi ve Ki-kare testi uygunluk fonksiyonu olarak seçilmiştir.
1) Shannon Entropi değerini hesapla : H(X) = - (p * (log2(p))) - ((1 - p) * (log2(1 - p)))
2) Ki-kare değerini hesapla: 2 = (gözlenen_H - beklenen_H)2/(beklenen_H)
3) Otokorelasyon katsayısını hesapla: φ2 (Phi-coefficient) = 2 / örnek_sayısı