DAFTAR PUSTAKA
1. Aguilar-Saven, R.S., (2004), “Business process modelling: review and framework”, International Journal of Production Economics 90, 129–149. 2. A. Osyczka. “Multicriteria Optimization for Engineering Design”, In J. S. Gero, editor, Design Optimization, pages 193–227. Academic Press, 1985. 3. Bititci, U.S., Muir, D., (1997), “Business process definition: a bottom-up approach”. The International Journal of Operations and Production Management 17 (4), 365–374. 4. Coello Coello Carlos.A, Lamont Gary B., Van Veldhuizen David A., (2007), “Evolutionary Algorithms for Solving Multi-Objective Problems”, Springer Science+Business Media,LLC. 5. Davenport, T. & Short, J., (1990), "The New Industrial Engineering: Information Technology and Business Process Redesign" Sloan Management Review. Massachusetts Institute of Technology: Cambridge. 6. Davenport, T.H., (1993), “Process Inovation : Reengineering Work Through Information Technology” , Boston, MA: Havard Business Press. 7. Deb .K, Agrawal, S., Pratap, A., Meyarivan, T., (2000), ”A fast elitist non-dominated sorting genetic algorithm for multiobjective optimization: NSGA-II”, KanGAL Report No. 200001. 8. Deb .K, (2001), “Multi-objective Optimisation Using Evolutionary Algorithms”. John & Wiley, New York. 9. Freschi, F., Repetto, M., (2005), “Multiobjective optimization by a modified artificial immune system algorithm”, Lecture Notes in Computer Science 3627, 248–261. 10. Goldberg, David E., (1989), “Genetic Algorithm in Search, Optimization & Machine Learning”, Addisson Wesley Publishing Co., Singapore. 11. Graham, D.W., Cassady, C.R., Bowden Jr, R.O. and Le May, S.A. (2000), “Model internal transportation system : establising a common language”, Technical report, Missipi State University, USA. 12. Hammer, M., Champy J., (1993), "Reengineering The Corporation", New York, Harper Collins Publishers. 13. Hofacker, I., Vetschera, R., (2001) “Algorithmical approaches to business process design”, Computers and Operations Research 28, 1253–1275.
xii
14. Harrington, H.J.,Dr., “Business Process Improvement : The Breakthrough Strategy for Total Quality Productivity and Competitiveness”, McGraw-Hill Inc,1991. 15. Kennedy, J., Eberhart, R., (1999), “The particle swarm: social adaptation in information-processing systems. In: Corne, D., Dorigo, M., Glover, F. (Eds.), New Ideas in Optimisation “,McGraw-Hill, Cambridge, pp. 379–388. 16. Kusiak. A., (1999) “Engineering Design-Products, Process, and Systems” Academic Press, A Harcourt Science and Technology Company, California, USA. 17. Kusiak A., Zakarian.A, (2000) “Analysis of Process Models”, IEEE Transaction on electronic pacaking manufacturing, vol.23,No.2, 137-147 18. Kusumadewi, Sri. (2003), ” Artificial Intelligence (Teknik dan Aplikasinya)”, Graha Ilmu, Yogyakarta. 19. Kusumadewi, Sri dan Purnomo, Hari., (2005), “Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik”, Graha Ilmu, Yogyakarta. 20. K.Vergidis, A.Tiwari, B.Majeed, and R.Roy, (2007), “Optimisation of business process designs : An Algorithmic approach with multiple objectives”, International Journal of Production Economics 109, 105–121. 21. Lakin, R., et al., (1996), “BPR enabling software for the financial services industry”, Management services, ISSN: 0307-6768. 22. Leyman, F & Altenhuber, W, (1994), “Managing business process as an information resources. IBM Systems”, Vol 33 No. 3, pp.326-348.Lieberman G.J., Hiller, F.S (1995), “Introduction to Operations Research”, McGraw-Hill, Singapore. 23. Lindsay, A., Downs,D., Lunn, K., (2003), “Business process-attemps to find a definition”, Information and Software Technology 45, pp.1015-1019. 24. Manganelli, Raymond L. & Klein (1994), “The Reengineering Handbook - A Step by Step Guide to Business Transformation”, New York, American Management Association. 25. Obitko, Marek, Introduction to Genetic Algorithms http://cs.felk.cvut.cz/~xobitko/ga/, 12 Desember 2007 214H
26. Phalp, K., et al., (1999), ”Quantitative analysis of static models of processes”, Journal of Systems and Software 52 (2), 105–112. 27. Saputro, Nico, “Algoritma Genetik”, Jurusan Teknik Elektro, Fakultas Teknologi Industri, Institut Teknologi Bandung, 1994. 28. Sbzarini Ivo F., Muller Sibylle , and Petros koumoutsakos (2000), ”Multiobjective optimization using evolutionary algorithms”, Proceeding of summer Program, Center for Turbulence Research, 63-74. 29. Suyanto (2005),”Algoritma Genetika dalam Matlab”, Penerbit Andi, Yogyakarta.
xiii
30. Wilhelm F.(Wilfred) van er Vegte, (2000), “Reference on Artifact Related Process Modelling”, Paper for EDIproD 2000 conference. 31. Zitzler, E. (1999), “Evolutionary algorithms for multiobjective optimization: Methods and applications”, Doctoral thesis ETH NO. 13398, Zurich: Swiss Federal Institute of Technology (ETH), Aachen, Germany: Shaker Verlag. 32. Lukman Felix, “Model Proses Bisnis”, tersedia on line http://www.felixlukman.happyhost.org/APB%202.ppt, diakses tanggal 3 Mei 2008.
di
215H
33. www.idef.com, diakses tanggal 12 November 2007. 216H
34. http://www.sipoel.unimed.in/file.php/44/COURSE)\, diakses tanggal 12 Juni 2008 217H
xiv
LAMPIRAN A • Coding Modifikasi Algoritma NSGA-II • Solusi Contoh Numerik 1
function main_nsga_2(pop,gen) %% function nsga_2(pop,gen) % merupakan fungsi optimasi yang multiobjective yang dimana argumentasi yang dimasukkan % adalah % pop - Ukuran Populasi % gen - Jumlah Generasi % % Fungsi ini didasarkan pada evolutionary algorithm untuk menemukan solusi optimal melalui % pareto front untuk seluruh fungsi tujuan yang multiple-objective. % Mulailah dengan memasukkan ukuran populasi dan jumlah total generasi yang diinginkan. if nargin < 2 error('NSGA-II.\nSilakan memasukkan jumlah populasi dan jumlah gen yang diinginkan.'); end % Input dari populasi dan generasi harus merupakan bilangan integer if isnumeric(pop) == 0 || isnumeric(gen) == 0 error('Data populasi dan data gen yang dimasukkan harus merupakan bilangan integer'); end % Populasi Minimum adalah 20 if pop < 20 error('Untuk menjalankan program ini, populasi minimum yang harus dimasukkan adalah 20'); end if gen < 5 error('Minimum generasi adalah 5'); end % Untuk memastikan bahwa data yang dimasukkan adalah integer pop = round(pop); gen = round(gen); %% Fungsi Tujuan % Penjelasan fungsi tujuan berisikan informasi fungsi tujuan yang ingin dicapai. % M merupakan dimensi dari fungsi tujuan, V merupakan dimensi dari aktivitas, W merupakan % total alternatif untuk seluruh aktivitas, c merupakan biaya yang di keluarkan untuk masing% masing alternatif dari aktivitas, dan q merupakan durasi untuk masing-masing alternatif dari % aktivitas. % Pastikan untuk mengedit "fungsi_evaluasi_tujuan" sesuai dengan % model yang telah anda digambarkan. [M, V, W, tc, c, d] = penjelasan_fungsi_tujuan(); %% Membangkitkan Populasi % Populasi dibangkitkan dengan bilangan random. % Setiap kromosom yang terbentuk terdiri dari setiap altenatif dari masing-masing % aktivitas, nilai dari masing-masing fungsi tujuan, ranking dan crowding distance. chromosome= inisialisasi_variabel(pop, M, V, W, tc, c, d); %% Mengurutkan Populasi % Populasi diurutkan dengan menggunakan non-domination-sort, sehingga akan % menghasilkan dua kolom untuk setiap individu yaitu ranking dan crowding % distance sesuai dengan posisinya dalam front. Untuk memudahkan % perhitungan maka nilai ranking dan crowding distance untuk setiap % kromosom ditambahkan pada vektor kromosom(vektor baris). chromosome = non_domination_sort_mod(chromosome, M, W); %% Memulai Proses Evolusi % Berikut ini adalah generasi. % * Memilih induk (parents) yang fit untuk melakukan reproduksi.
% * Setelah memilih induk (parents) yang fit, lakukan Crossover dan Mutation % * Lakukan kembali Seleksi dari parents dan offspring yang telah terbentuk. % * Ganti individu yang tidak fit dengan individu yang fit untuk mempertahankan ukuran % * populasi. for i = 1 : gen % Memilih individu yang akan dijadikan induk (parents) % Seleksi akan menetukan individu-individu mana saja yang akan dipilih % sebagai induk untuk dilakukan rekombinasi dan bagaimana offspring % terbentuk dari individu induk yang terpilih tersebut. % Algoritma NSGA-II yang original menggunakan seleksi binary turnamen % berdasarkan perbandingan crowding distance. % Parameter yang digunakan adalah : % pool - ukuran dari mating pool. Hal ini akan menjadikan % setengahnya dari ukuran populasi. % tour - ukuran tour. % pool = round(pop/2); tour = 2; % Proses Seleksi % Pada proses seleksi binary tournament, 2 individu terbaik akan % dipilih sebagai induk yang dipilih secara random dari % suatu populasi dan diperbandingkan nilai fitnessnya. % Seleksi turnamen dilanjutkan sampai ukuran kolom % diisi semua. Pada dasarnya ukuran kolom (pool) merupakan jumlah % individu-individu induk yang telah dipilih. Parameter yang digunakan % dalam proses seleksi binary tournament adalah chromosome, pool, % tour. Fungsi ini hanya menggunakan informasi dari 2 elemen terakhir % dalam vektor kromosom, yaitu nilai rank dan nilai crowding distance. % Proses seleksinya didasarkan pada nilai rank, yang dimana apabila % nilai rank sama maka crowding distance yang diperbandingkan. % Kriteria seleksi ini adalah memlilih Rank yang paling kecil dan nilai % crowding distance yang jauh. parent_chromosome = seleksi_turnamen(chromosome, pool, tour); % % Melakukan proses penyilangan (Crossover) dan Mutasi (Mutation) % Modifikasi algoritma NSGA-II menggunakan one point crossover dan % mutasi biner. % Peluang crossover (pc) adalah 0.8, maka diharapkan 80 % dari total % kromosom akan mengalami crossover. % Untuk memilih kromosom-kromosom mana saja yang akan % dilakukan crossover, bangkitkan nilai acak antara [0 1]. % Crossover (penyilangan) dilakukan atas 2 kromosom untuk % menghasilkan kromosom anak (offspring). % Metode crossover yang digunakan adalah crossover satu titik % (one-point crossover) % Pilih bilangan acak yang kurang dari pc, maka kromosom itu % berhak melakukan crossover. % Pemilihan posisi penyilangan dengan mengambil bilangan acak, % kemudian dilanjutkan dengan penyilangan ini juga dilanjutkan % untuk semua pasangan kromosom yang disilangkan. % % % %
% Mutasi yang digunakan adalah mutasi biner yaitu dengan mengganti satu atau beberapa nilai gen dari kromosom itu. Pada dasarnya mutasi ini akan mengubah secara acak nilai suatu bit pada posisi tertentu. Kemudian kita akan mengganti nilai bit 1 dengan 0, atau
% % %
mengganti bit 0 dengan 1. Pada mutasi ini sangat dimungkinkan kromosom baru yang semula belum muncul dalam populasi awal. pc = 0.8 ; % pc = crossover probability offspring_chromosome = ... genetic_operator(parent_chromosome, ... M,tc,W,c,d,pc); % Intermediate population % Intermediate population merupakan kombinasi populasi induk dan % offspring dari generasi yang dilakukan. Ukuran generasi menjadi dua % kali lipat dari populasi awal. [main_pop,temp] = size(chromosome); [offspring_pop,temp] = size(offspring_chromosome); % temp merupakan variabel dummy. clear temp % intermediate_chromosome digabungkan dengan populasi awal dan populasi % offspring. intermediate_chromosome(1:main_pop,:) = chromosome; intermediate_chromosome(main_pop + 1 : main_pop + offspring_pop,1 : M+W) = ... offspring_chromosome;
% Non-domination-sort of intermediate population % Populasi awal + offspring (intermediate population) kemudian % diurutkan kembali berdasarkan non-domination sort sebelum dilakukan % pergantian (replacement) antara populasi. intermediate_chromosome = ... non_domination_sort_mod(intermediate_chromosome, M, W); % Melakukan Seleksi kembali % Sekali lagi, intermediate population diurutkan berdasarkan solusi % kriteria terbaik berdasarkan rank dan crowding distance. chromosome = replace_chromosome(intermediate_chromosome, M, W,pop) fprintf('%d generations completed\n',i); end %% Hasil % simpan hasil dalam format ASCII text. save solution.txt chromosome -ASCII %% Visualisasi % Berikut ini hasil visualisasi berdasarkan dimensi fungsi tujuan yang % dimasukkan. (Elty Sarvia) if M == 2 plot(chromosome(:,(W+1)),chromosome(:,(W+2)),'*'); title('Multiobjective for 2 objective function ','fontsize',12); xlabel('f(x_1) Durasi'); ylabel('f(x_2) Cost'); elseif M ==3 plot3(chromosome(:,(W+1)),chromosome(:,(W+2)),chromosome(:,(W+3)),'*'); title('Multiobjective for 3 objective function'); xlabel('f(x_1)'); ylabel('f(x_2)'); zlabel ('f(x_3)'); end
function [jumlah_fungsi_tujuan, jumlah_aktivitas, total_alternatif, titik_crossover, c, d] = penjelasan_fungsi_tujuan() %% function [jumlah_fungsi_tujuan, jumlah_pembatas, jumlah_aktivitas, jumlah_alternatif, c, q] % = penjelasan_fungsi_tujuan() % Fungsi ini digunakan untuk menjelaskan fungsi tujuan apa saja yang digunakan, % jumlah aktivitas dan alternatif yang terdapat dalam suatu proses bisnis yang telah % dimodelkan sebelumnya. % Silakan anda memasukkan jumlah fungsi tujuan, jumlah aktivitas dan jumlah alternatif yang % digunakan. Setelah itu, fungsi dalam program akan menunggu pengguna untuk memodifikasi fungsi % evaluasi_fungsi_tujuan untuk disesuaikan dengan menyesuaikan pada model yang telah digambarkan % sebelumnya. g = sprintf('Masukkan Jumlah Fungsi Tujuan yang Diinginkan: '); % Untuk Mendapatkan Jumlah Fungsi Tujuan jumlah_fungsi_tujuan = input(g); if jumlah_fungsi_tujuan < 2 error('Program ini dipergunakan untuk fungsi optimasi yang memiliki minimal 2 fungsi tujuan, sehingga jumlah fungsi tujuan yang dimasukkan minimal 2'); end g = sprintf('\nMasukkan Jumlah Aktivitas Yang Diinginkan: '); % Untuk Mendapatkan Jumlah Pembatas jumlah_aktivitas = input(g); biaya=[]; durasi=[]; titik_crossover=[] for i = 1 : jumlah_aktivitas fprintf(1,'aktivitas = % 4d \n',i) g = sprintf('\nMasukkan Jumlah Alternatif Yang Diinginkan: '); % Untuk Mendapatkan Jumlah Alternatif jumlah_alternatif = input(g); % Untuk mengenerate cost dari setiap alternatif aktivitas for ii = 1 : jumlah_alternatif g = sprintf('\nBiaya yang dikeluarkan alternatif %d : ', ii); cost = input(g); biaya = [biaya cost]; % Untuk Mengenerate array durasi dari setiap alternatif aktivitas g = sprintf('\nDurasi yang dikeluarkan aktivitas alternatif %d : ', ii); duration = input(g); durasi =[durasi duration]; end tc=jumlah_alternatif; titik_crossover=[titik_crossover tc]; end c = biaya; d = durasi; total_alternatif=sum(titik_crossover); titik_crossover g = sprintf('\n Silakan mengubah function "evaluasi_fungsi_tujuan" sesuai \n dengan model yang anda gambarkan. \n Pastikan jumlah fungsi tujuan, jumlah aktivitas dan jumlah alternatif sesuai dengan yang telah dimasukkan.\n Sesuaikan fungsi tujuan sudah dihubungkan dengan matriks.\n Silakan tekan tombol "c" dan tekan enter untuk melanjutkan program ini...'); % Menganjurkan user untuk mengedit evaluasi_fungsi _tujuan dan menunggu
% sampai tombol c di tekan. x = input(g, 's'); if isempty(x) x = 'x'; end while x ~= 'c' clc x = input(g, 's'); if isempty(x) x = 'x'; end end
function f = inisialisasi_variabel(N,M,V,W,tc,c,d) %% function f = inisialisasi_variabel(N,M,V,W,tc,c,d) % Fungsi ini untuk membangkitkan populasi dari kromosom sesuai dengan jumlah aktivitas dalam proses % bisnis dan tujuannnya dimana % N - Ukuran populasi % M - Jumlah fungsi tujuan % V - Jumlah aktivitas % W - Jumlah total alternatif untuk seluruh aktivitas % tc - Jumlah alternatif untuk setiap aktivitas % c _ Biaya dari setiap alternatif aktivitas % d _ Durasi dari setiap alternatif aktivitas % K adalah total matriks elemen yang di-generate. % Untuk memudahkan perhitungan, maka setiap alternatif dari setiap aktivitas dan fungsi tujuan % digabungkan/dirangkaikan bersamaan dengan setiap matriks yang terbentuk. % Crossover dan mutation hanya menggunakan alternatif dari setiap aktivitas, sedangkan untuk Seleksi % hanya menggunakan variabel fungsi tujuan. K=M+W; %% Membangkitkan setiap kromosom. W; % W adalah total alternatif untuk semua aktivitas so = []; tc = tc' for i = 1 : V tcc=tc(i); p= zeros(1,tcc); B= ones(1,tcc); p(1,[1])=B(1,1); so = [so p]; end to = []; tc = tc' for i = 1 : V tcc=tc(i); p= zeros(1,tcc); B= ones(1,tcc); p(1,[tcc])=B(1,1); to = [to p]; end xo = [so ; to]; bil_random = rand (N,1); for i = 1 : N % N adalah jumlah populasi for j = 1 : length(tc) if bil_random(i,1)<=j/2 f(i,:)=xo(j,:); break end end end for i = 1 : N c; d; f (i,W+1:K )= evaluasi_fungsi_tujuan(f(i,:), M, W, c, d); end
function f = evaluasi_fungsi_tujuan(x,M,W,c,d) %% Untuk contoh numerik 1 %% function f = evaluasi_fungsi_tujuan(x, M, W, c, d) % Fungsi ini digunakan untuk mengevaluasi vektor yang diinput yaitu x. % x adalah merupakan matriks dari setiap aktivitas dan alternatif yang digambarkan dengan % IDEF 3, f(1), f(2) yang merupakan fungsi tujuan. Algoritma ini selalu meminimasi fungsi objektif % sehingga apabila untuk fungsi yang ingin dimaksimasi maka harus mengkalikan fungsi itu dengan % bilangan negatif. % M merupakan jumlah fungsi tujuan yang ingin dicapai. % V merupakan jumlah aktivitas dalam suatu proses bisnis yang dijalankan. % W merupakan jumlah total alternatif dari seluruh aktivitas yang ada % c merupakan biaya dari setiap alternatif aktivitas % d merupakan durasi dari setiap alternatif aktivitas % Fungsi dibawah ini didasarkan pada model yang digambarkan berdasarkan model IDEF 3 dalam suatu % proses bisnis pada Travel Agents dengan 4 aktivitas, dan masing-masing aktivitas mempunyai 2 % alternatif dengan durasi dan biaya yang berbeda satu sama lainnya. Mohon Periksa kembali bentuk % fungsi dan input yang akan digunakan sesuai dengan kebutuhan dari user. % Fungsi Tujuan Yang Pertama yaitu Minimasi Durasi f = []; dpil_1=(d(1).*x(1))+(d(2).*x(2))+(d(5).*x(5))+(d(6).*x(6)); dpil_2=(d(3).*x(3))+(d(4).*x(4))+(d(7).*x(7))+(d(8).*x(8)); [dj] = max(dpil_1,dpil_2) f(1) = dj; % Fungsi Tujuan Yang Kedua yaitu Minimasi Biaya sum=0; for ki = 1 : W sum = sum +((c(ki)).*x(ki)); end f(2) = sum;
function f = non_domination_sort_mod(x, M, W) %% function f = non_domination_sort_mod(x, M, W) % Fungsi ini mengurutkan populasi saat ini berdasarkan non-domination. % Semua individu yang berada pada front yang pertama diberi nilai rank sama dengan 1, sedangkan pada % front kedua individu diberi nilai rank sama dengan 2. setelah dilakukan perhitungan rank, maka % selanjutnya adalah perhitungan crowding distance. [N, m] = size(x); clear m K=M+W; % VW=V*W; % Inisialisasi front number = 1. front = 1; F(front).f = []; individual = []; %% Non-Dominated sort. % Inisialisasi populasi diurut berdasarkan non-domination. Algoritma adalah % sbb: % % Untuk setiap individu p dalam populasi yang utama P, dilakukan : % – Inisialisasi Sp=Ø, yang nantinya akan berisikan semua individu% individu yang didominasi oleh p. % – Inisialisasi np = 0, yang merupakan jumlah individu-individu yang % mendominasi p. % – Untuk setiap individu q di dalam P % *Jika p mendominasi q maka: % · Tambahkan q pada kumpulan Sp yaitu Sp= Sp U {q} % *Jika q mendominasi p maka: % · Sehingga np= np + 1 % – Jika np = 0 yaitu tidak terdapat individu yang mendominasi p sehingga % p merupakan front yang pertama dan kemudian individu p diberi rank 1 % seperti prank = 1. Update front yang pertama dengan menambahkan p % pada front yang pertama yaitu F1 = F1 U {p} % • Hal ini nantinya akan mengeluarkan semua individu-individu yang berada % dalam Populasi utama P. % • Inisialisasi front = 1 --> i=1 % • Dilakukan pada front ke-i sehingga Fi tidak sama dengan Ø % – Q = Ø merupakan penyimpanan kumpulan individu-individu untuk front ke (i+1). % – Untuk setiap individu p di dalam Front Fi % * Setiap individu q yang berada dalam Sp (Sp berisikan semua % individu-individu yang didominasi oleh p) % · nq = nq-1, pengurangan individu q. % · Jika nq = 0 , tidak terdapat individu-individu pada front % yang berikutnya yang mendominasi q. Akibatnya ubah qrank = i+1 % dan update Q dengan menambahkan individu q yaitu Q = Q U q. % – Tambahkan counter front dengan 1 % – Kemudian ubah Q menjadi front berikutnya sehingga Fi = Q % Algoritma ini lebih baik jika dibandingkan dengan Original NSGA sejak menggunakan informasi % mengenai kumpulan individu yang mendominasi (Sp) dan jumlah individu-individu yang % mendominasi suatu individu (np) for i = 1 : N % Jumlah individu-individu yang mendominasi satu individu np=0
individual(i).n = 0; % Satu individu mendominasi individu-individu yang lain Sp=[] individual(i).p = []; for j = 1 : N dom_less = 0; dom_equal = 0; dom_more = 0; for k = 1 : M if [x(i,(W+k)) < x(j,(W+k))] dom_less = dom_less + 1; elseif [x(i,(W+k)) == x(j,(W+k))] dom_equal = dom_equal + 1; else dom_more = dom_more + 1; end end if dom_less == 0 && dom_equal ~= M individual(i).n = individual(i).n + 1; elseif dom_more == 0 && dom_equal ~= M individual(i).p = [individual(i).p j]; end end if individual(i).n == 0 x(i,(K+1)) = 1; F(front).f = [F(front).f i]; end end % Mencari front-front berikutnya while ~isempty(F(front).f) Q = []; for i = 1 : length(F(front).f) %front ke -i if ~isempty(individual(F(front).f(i)).p) for j = 1 : length(individual(F(front).f(i)).p) individual(individual(F(front).f(i)).p(j)).n = ... individual(individual(F(front).f(i)).p(j)).n - 1; if individual(individual(F(front).f(i)).p(j)).n == 0 x(individual(F(front).f(i)).p(j),(K+1)) = ... front + 1; Q = [Q individual(F(front).f(i)).p(j)]; end end end end front = front + 1; F(front).f = Q; end K=M+W; [temp,index_of_fronts] = sort(x(:,K+1)); for i = 1 : length(index_of_fronts) sorted_based_on_front(i,:) = x(index_of_fronts(i),:); end current_index = 0; %% Crowding distance % Untuk perhitungan crowding distance dilakukan sebagai berikut : % • Pada setiap front Fi, n merupakan jumlah individu-individu % – Inisialisasi jarak (distance) untuk semua individu-individu dengan nilai 0
% yaitu Fi (dj) = 0, dimana j adalah individu ke-j di dalam front Fi. % – Pada setiap fungsi tujuan m % * Urutan semua individu-individu di dalam front Fi berdasarkan % fungsi tujuan m yaitu I = sort (Fi,m) % * Untuk pertama kali, berikan nilai jarak (distance) untuk setiap % individu dalam front Fi sama dengan tak terhingga yaitu I(dI) = ~ % dan I(dn) = ~ % * untuk k = 2 sampai (n - 1) % · I(dk) = I(dk) + (I(k + 1).m - I(k - 1).m)/fmax(m) - fmin(m) % · I(k). m adalah nilai fungsi tujuan mth dari individu kth di I. % Mencari nilai crowding distance untuk masing-masing individu di dalam setiap front for front = 1 : (length(F) - 1) % objective = []; distance = 0; y = []; previous_index = current_index + 1; for i = 1 : length(F(front).f) y(i,:) = sorted_based_on_front(current_index+i,:); end current_index = current_index + i; % Urutkan masing-masing individu berdasarkan objective-nya sorted_based_on_objective = []; for i = 1 : M [sorted_based_on_objective, index_of_objectives] = ... sort(y(:,(W+i))); sorted_based_on_objective = []; for j = 1 : length(index_of_objectives) sorted_based_on_objective(j,:) = y(index_of_objectives(j),:); end f_max = ... sorted_based_on_objective(length(index_of_objectives), (W+i)); f_min = sorted_based_on_objective(1, (W + i)); y(index_of_objectives(length(index_of_objectives)),K+1+i)... = Inf; y(index_of_objectives(1),K+1+i) = Inf; for j = 2 : length(index_of_objectives) - 1 next_obj = sorted_based_on_objective(j + 1,(W+i)); previous_obj = sorted_based_on_objective(j - 1,(W+i)); if (f_max - f_min == 0) y(index_of_objectives(j),K+1+i) = Inf; else y(index_of_objectives(j),K+1+i) = ... (next_obj - previous_obj)/(f_max - f_min); end end end distance = []; distance(:,1) = zeros(length(F(front).f),1); for i = 1 : M distance(:,1) = distance(:,1) + y(:,K+1+i); end y(:,K+2) = distance; y = y(:,1 : K+2); z(previous_index:current_index,:) = y; end f = z();
function f = seleksi_turnamen(chromosome, pool_size, tour_size) %% f = seleksi_turnamen(chromosome, pool_size, tour_size) % merupakan seleksi untuk memilih induk untuk mating pool. Pemilihannya berdasarkan seleksi % turnamen. Setelah dilakukan turnamen seleksi dengan ukuran turnamen yaitu |tour_size|, kromosom % pada populasi dalam generasi tersebut yang mana individunya dipilih untuk menjadi mating pool dari % size |pool_size|.Untuk NSGA-II ukuran tour yang ditetapkan adalah 2. %% Proses Seleksi Turnamen. % Pada proses turnamen n individu dipilih secara random, dimana n harus sama jumlahnya dengan % ukuran |tour_size|. Dari individu ini yang terpilih hanya satu yang akan dipilih dan ditambahkan ke % mating pool, dan mating pool adalah |pool_size|. % Seleksi dilakukan berdasarkan 2 kriteria yaitu yang pertama adalah mencari rank yang paling kecil, % dan bila ditemukan nilai rank dari kedua individu sama maka nilai crowding distance yang % diperbandingkan.Individu dengan nilai crowding distance yang terbesar yang akan dipilih. % Mencari ukuran chromosome dimana jumlah chromosome tidaklah penting, % sementara jumlah elemen dalam chromosome yang lebih penting. [pop, variables] = size(chromosome); % elemen kedua terakhir yang berisikan informasi rank. rank = variables - 1; % elemen terakhir yang berisikan informasi crowding distance. distance = variables; % Sampai mating pool diisi semua, dilakukan seleksi turnamen. for i = 1 : pool_size % Pilih n individu secara random, dimana n = tour_size for j = 1 : tour_size % Pilih satu individu secara random candidate(j) = round(pop*rand(1)); % Pastikan dimulai dari array yang pertama. if candidate(j) == 0 candidate(j) = 1; end if j > 1 % Pastikan kandidat yang sama tidak terpilih. while ~isempty(find(candidate(1 : j - 1) == candidate(j))) candidate(j) = round(pop*rand(1)); if candidate(j) == 0 candidate(j) = 1; end end end end % Mengumpulkan informasi mengenai semua kandidat yang terpilih. for j = 1 : tour_size c_obj_rank(j) = chromosome(candidate(j),rank); c_obj_distance(j) = chromosome(candidate(j),distance); end % Mencari kandidat yang memiliki rank terkecil. min_candidate = ... find(c_obj_rank == min(c_obj_rank)); % Jika lebih dari satu kandidat yang memiliki nilai rank terkecil, maka % cari kandidat dalam group yang memiliki nilai max crowding distance. if length(min_candidate) ~= 1 max_candidate = ... find(c_obj_distance(min_candidate) == max(c_obj_distance(min_candidate)));
% Jika sedikit individu yang memiliki rank terkecil dan max crowding % distance, maka pilih hanya satu individu (tidak perlu random) if length(max_candidate) ~= 1 max_candidate = max_candidate(1); end % Tambahkan individu yang terpilih ke dalam the mating pool f(i,:) = chromosome(candidate(min_candidate(max_candidate)),:); else % Tambahkan individu yang terpilih ke dalam the mating pool f(i,:) = chromosome(candidate(min_candidate(1)),:); end end
function f = genetic_operator(parent_chromosome,M,tc,W,c,d,pc) %% function f = genetic_operator(parent_chromosome,M,V,W,c,d,pc) % Fungsi ini digunakan untuk menghasilkan keturunan dari kromosom induk. % Operator genetika seperti crossover dan mutasi mengalami sedikit modifikasi dari desain originalnya. % parent_chromosome - kromosom yang terpilih sebagai induk % V merupakan jumlah aktivitas dalam suatu proses bisnis yang dijalankan. % W merupakan jumlah total alternatif dari seluruh aktivitas yang ada % c merupakan biaya dari setiap alternatif aktivitas % d merupakan durasi dari setiap alternatif aktivitas % pc merupakan probabilitas crossover % (Elty) [N,m] = size(parent_chromosome); clear m p = 1; % tanda yang digunakan bahwa crossover dan mutation dimulai was_crossover = 0; was_mutation = 0; for i = 1 : N % dengan pc = 80 % if rand(1) < pc % vektor keturunan diinisialisasi = 0 child_1 = []; child_2 = []; % Pilih induk yang pertama parent_1 = round(N*rand(1)); if parent_1 < 1 parent_1 = 1; end % Pilih induk yang kedua parent_2 = round(N*rand(1)); if parent_2 < 1 parent_2 = 1; end % Untuk memastikan bahwa kedua induk itu tidak dari baris yang sama while isequal(parent_chromosome(parent_1,:),parent_chromosome(parent_2,:)) parent_2 = round(N*rand(1)); if parent_2 < 1 parent_2 = 1; end end % Hanya untuk mengetahui informasi kromosom mana yang % dipilih secara random sebagai induk parent_1 = parent_chromosome(parent_1,:); parent_2 = parent_chromosome(parent_2,:); % Lakukan crossover kum_tc=cumsum(tc) acak_kromosom=randperm(length(tc)); acak_1 = acak_kromosom(1); if acak_1 == 1 pos =kum_tc(1,1) ; else
pos =kum_tc(1,acak_1); end % Lakukan one point crossover berdasarkan titik potong yang % dipilih secara random melalui bilangan acak tmp11 = parent_1(1,1:pos); tmp12 = parent_1(1,pos+1:W); tmp21 = parent_2(1,1:pos); tmp22 = parent_2(1,pos+1:W); child_1(1,1:pos)=tmp11; child_1(1,pos+1:W)=tmp22; child_2(1,1:pos)=tmp21; child_2(1,pos+1:W)=tmp12; % Keturunan yang terbentuk setelah crossover child_1; child_2; K=M+W; % Evaluasi fungsi tujuan pada keturunan yang terbentuk child_1(:,W + 1: K) = evaluasi_fungsi_tujuan(child_1, M, W, c, d); child_2(:,W + 1: K) = evaluasi_fungsi_tujuan(child_2, M, W, c, d); % Bila crossover sudah terjadi maka berikan tanda % Crossover akan menghasilkan dua buah keturunan sedangkan Mutation % hanya menghasikan satu keturunan saja. was_crossover = 1; was_mutation = 0; % Jika 20 %, maka Mutasi yang akan terjadi. Mutasi disini juga mengalami modifikasi bila %dibandingkan dengan algoritma. NSGA-II yang original yaitu menggunakan mutasi biner. else % Pilih induk secara random. parent_3 = round(N*rand(1)); if parent_3 < 1 parent_3 = 1; end child_3 = parent_chromosome(parent_3,1:W) % Mengenerate bilangan acak secara permutasi dari jumlah aktivitas kum_tc=cumsum(tc) mut=1; % apabila pada aktivitas hanya terdapat 1 alternatif, maka % tidak dilakukan mutasi while (length (mut(1,:)) == 1) acak_kromosom=randperm(length(tc)); acak_1 = acak_kromosom(1); poss = tc(1,acak_1); if acak_1 == 1 pos1 = 1; pos2 =kum_tc(1,acak_1); mut = child_3(1,pos1:pos2); else pos1 = (kum_tc(1,(acak_1-1))+1); pos2 =kum_tc(1,acak_1); mut = child_3(1,(pos1:pos2)); end end % Lakukan mutasi biner pada aktivitas yang terpilih for ij = 1 : poss
if mut(1,ij) == 1 if (ij < poss) mut(1,ij)= 0 mut(1,(ij+1))= 1 break else mut(1,ij)= 0 mut(1,(ij-1))= 1 break end end end mut if pos1 ~= 1 temp1=child_3(1,1:pos1); temp2=mut; temp3=child_3(1,pos2+1:W); child_3(1,1:pos1) = temp1; child_3(1,pos1:pos2) = temp2; child_3(1,pos2+1:W) = temp3; else temp1=mut temp2=child_3(1,pos2+1:W); child_3(1,1:pos2) = temp1; child_3(1,pos2+1:W) = temp2; end %
Keturunan baru setelah mutasi child_3;
K=M+W; % Evaluasi fungsi tujuan pada keturunan yang terbentuk child_3(:,W + 1 : K) = evaluasi_fungsi_tujuan(child_3, M, W, c, d); % % Berikan tanda apabila mutasi selesai dilaksanakan was_mutation = 1; was_crossover = 0; end % % Untuk semua keturunan yang telah digenerate pada setiap generasi if was_crossover child(p,:) = child_1; child(p+1,:) = child_2; was_crossover = 0; p = p + 2; elseif was_mutation child(p,:) = child_3; was_mutation = 0; p = p + 1; end end f = child; %
function f = replace_chromosome(intermediate_chromosome, M, W,pop) %% function f = replace_chromosome(intermediate_chromosome, M, W,pop) % Fungsi ini akan menempatkan kembali kromosom berdasarkan rank dan crowding distance. Inisialisasi % sampai ukuran populasi pada masing-masing front sama dengan nilai N yang pertama kali. [N, m] = size(intermediate_chromosome); K=M+W; % Mengetahui indeks dari pengurutan populasi berdasarkan rank [temp,index] = sort(intermediate_chromosome(:,K+1)); clear temp m % Sekarang dilakukan pengurutan atas semua individu berdasarkan indeksnya for i = 1 : N sorted_chromosome(i,:) = intermediate_chromosome(index(i),:) end % Mencari nilai rank yang maksimum pada populasi tersebut. max_rank = max(intermediate_chromosome(:,K+1)); % Mulai mengisi populasi berdasarkan rank dan crowding distance previous_index = 0; for i = 1 : max_rank % Mencari nilai indeks dari rank tersebut contoh elemen terakhir pada % saat pengurutan kromosom dengan rank i, current_index = max(find(sorted_chromosome(:,K+1) == i)) % Mengecek populasi telah diisi jika semua individu-individu dengan % rank 1 sudah ditambahkan ke populasi if current_index > pop % cek yang masih tersisa remaining = pop - previous_index; % Mengetahui informasi individu-individu pada current rank i temp_pop = ... sorted_chromosome(previous_index + 1 : current_index, :); % Urutkan individu-individu dengan nilai rank dan nilai crowding % distance dengan nilai yang menurun (descending) [temp_sort,temp_sort_index] = ... sort(temp_pop(:,K + 2),'descend'); % Replace chromosome dengan mengisi individu-individu ke dalam % populasi dengan hitungan menurun. for j = 1 : remaining f(previous_index + j,:) = temp_pop(temp_sort_index(j),:); end return; elseif current_index < pop % Tambahkan semua individu dengan rank i ke dalam populasi. f(previous_index + 1 : current_index, :) = ... sorted_chromosome(previous_index + 1 : current_index, :); else % Tambahkan semua individu dengan rank i ke dalam populasi. f(previous_index + 1 : current_index, :) = ... sorted_chromosome(previous_index + 1 : current_index, :); return; end % Mencari nilai indeks dari nilai individu terakhir yang ditambahkan. previous_index = current_index; end
LAMPIRAN B • Coding “Evaluasi fungsi tujuan” Modifikasi Algoritma NSGA-II • Solusi Contoh Numerik 2
function f = evaluasi_fungsi_tujuan(x,M,W,c,d) %% Untuk Contoh Numerik 2 %% function f = evaluasi_fungsi_tujuan(x, M, W, c, d) % Fungsi ini digunakan untuk mengevaluasi vektor yang diinput yaitu x. % x adalah merupakan matriks dari setiap aktivitas dan alternatif yang % digambarkan dengan IDEF 3, f(1), f(2) yang merupakan fungsi tujuan. % Algoritma ini selalu meminimasi fungsi objektif sehingga apabila % duntuk fungsi yang ingin imaksimasi maka harus mengkalikan % fungsi itu dengan bilangan negatif. % M merupakan jumlah fungsi tujuan yang ingin dicapai. % V merupakan jumlah aktivitas dalam suatu proses bisnis yang dijalankan. % W merupakan jumlah alternatif dari setiap aktivitas yang ada % c merupakan biaya dari setiap alternatif aktivitas % d merupakan durasi dari setiap alternatif aktivitas % Fungsi dibawah ini didasarkan pada model yang digambarkan berdasarkan % model IDEF 3 pada contoh numerik 3 % Mohon Periksa kembali bentuk fungsi dan input yang akan digunakan sesuai % dengan kebutuhan dari user. % Fungsi Tujuan Yang Pertama yaitu Minimasi Durasi f = []; dpil_1=((d(1).*x(1))+(d(2).*x(2))+(d(3).*x(3))+(d(4).*x(4))+.... .... (d(5).*x(5))) dpil_2=((d(1).*x(1))+(d(2).*x(2))+(d(3).*x(3))+.... .... (d(6).*x(6))+(d(7).*x(7))) dpil_3=((d(1).*x(1))+(d(2).*x(2))+(d(3).*x(3))+ .... .... (d(8).*x(8))+(d(9).*x(9))) dpil_4=((d(1).*x(1))+(d(2).*x(2))+(d(3).*x(3))+.... .... (d(10).*x(10))+(d(11).*x(11))) [dmax1] = max(dpil_1,dpil_2) [dmax2] = max(dpil_3,dpil_4) [dj] = max(dmax1,dmax2) f(1) = dj % Fungsi Tujuan Yang Kedua yaitu Minimasi Biaya sum=0; for ki = 1 : W sum = sum +((c(ki)).*x(ki)); end f(2) = sum;
LAMPIRAN C • Coding “Evaluasi fungsi tujuan” Modifikasi Algoritma NSGA-II • Solusi Contoh Numerik 3
function f = evaluasi_fungsi_tujuan(x,M,W,c,d) %% Untuk Contoh Numerik 3 %% function f = evaluasi_fungsi_tujuan(x, M, W, c, d) % Fungsi ini digunakan untuk mengevaluasi vektor yang diinput yaitu x. % x adalah merupakan matriks dari setiap aktivitas dan alternatif yang % digambarkan dengan IDEF 3, f(1), f(2) yang merupakan fungsi tujuan. % Algoritma ini selalu meminimasi fungsi objektif sehingga apabila untuk % fungsi yang ingin dimaksimasi maka harus mengkalikan fungsi itu dengan % bilangan negatif. % M merupakan jumlah fungsi tujuan yang ingin dicapai. % V merupakan jumlah aktivitas dalam suatu proses bisnis yang dijalankan. % W merupakan jumlah alternatif dari setiap aktivitas yang ada % c merupakan biaya dari setiap alternatif aktivitas % d merupakan durasi dari setiap alternatif aktivitas % Fungsi dibawah ini didasarkan pada model yang digambarkan berdasarkan % model IDEF 3 dalam suatu proses bisnis pada contoh numerik 3 % Mohon Periksa kembali bentuk fungsi dan input yang akan digunakan sesuai % dengan kebutuhan dari user. % Fungsi Tujuan Yang Pertama yaitu Minimasi Durasi f = []; dpil_1=((d(1).*x(1))+(d(2).*x(2))+(d(3).*x(3))+(d(4).*x(4))+.... .... ((d(5).*x(5))+d(6).*x(6))+(d(7).*x(7))+(d(8).*x(8))) dpil_2=((d(1).*x(1))+(d(2).*x(2))+(d(3).*x(3))+(d(4).*x(4))+.... .... (d(5).*x(5))+(d(9).*x(9))+(d(10).*x(10))) [dj] = max(dpil_1,dpil_2) f(1) = dj % Fungsi Tujuan Yang Kedua yaitu Minimasi Biaya sum=0; for ki = 1 : W sum = sum +((c(ki)).*x(ki)); end f(2) = sum;
