## PENERAPAN COCKROACH SWARM OPTIMIZATION ALGORITHM (CSOA) PADA PENYELESAIAN

## PERSAMAAN POLINOMIAL YANG MEMILIKI AKAR KOMPLEKS
( Implementation of Cockroach Swarm Optimization Algorithm ( CSOA ) to Solve
Polynomial Equations with Complex Roots )

## Ema Fahma Farikha, Rusli Hidayat, M. Ziaul Arif
Jurusan Matematika, Fakultas MIPA, Universitas Jember Jl. Kalimantan 37 Jember 68121, Indonesia
E-mail: emafarikha01@gmail.com
Abstract. In this paper, we use a metaheuristic algorithm for solving non-linear equations (polynomial equations) which have a set of complex roots (complex numbers).  The  metaheuristic  algorithm  is  the  Cockroach  Swarm  Optimization Algorithm (CSOA) which imitate various types of natural cockroach behaviors such  as  chase-swarming,  dispersing  and  ruthlessness  when  hunting  for  food sources. In this study, several examples of non-linear polynomial equations were used  for  evaluating  the  accuracy  of  CSOA.  In  this  simulation,  the  accuracy comparison  has  been  accomplished.  It  is  shown  that  CSOA  results  are  more accurate compared to the Newton-Raphson results.
Keywords: Cockroach  Swarm  Optimization  Algorithm,  Complex  roots  of polynomial, Newton-Raphson, Non-Linear equation.
MSC2010: 90B05

## 1. Pendahuluan
Pencarian solusi persamaan non linier masih menjadi kajian yang menarik untuk dibahas dalam  penelitian.  Dalam  sedikit  kasus,  pencarian  solusi  persamaan  tersebut  dapat diselesaikan secara analitik. Akan tetapi pada kasus global yang kompleks, penyelesian permasalahan  tersebut  sangat  sulit  dilakukan  secara  analitik.  Sehingga,  alternatif pencarian  solusi  dapat  dilakukan  dengan  menggunakan  metode  numerik.  Beberapa metode  numerik  sederhana  seperti  metode Newton-Raphson , Secant ,  iterasi  titik  tetap, dan  metode  bagi  dua  ( Bisection )  mampu  menyelesaikan  persamaan  non  linier.  Akan tetapi, metode tersebut memerlukan syarat-syarat tertentu agar konvergen menuju solusi yang diinginkan seperti nilai awal, selang solusi, gradien dari tebakan awal, dan lain-lain. Hal ini yang membuat metode tersebut kurang efisien dan efektif.  Dalam dekade terakhir, penggunaan  metode  metaheuristik  menjadi  alternatif  metode  numerik  karena  efisiensi dalam penyelesaian permasalahan yang kompleks.
Topik  penelitian  yang  menggunakan  algoritma  metaheuristik  dalam  permasalahan matematika sudah dilakukan pada [1, 3, 7]. Pada [1], gabungan metode zero crossing dan virus evolutionary genetic algorithm (Vega) efektif dalam mencari akar persamaan non linier. Selanjutnya pada [3], algoritma Cat Swarm Optimization (CSO) mampu mencari solusi  yang akurat suatu  Sistem Persamaan Non-linier dengan hanya memberikan nilai awal  sekumpulan  calon  solusi  yang  berupa  bilangan  random.  Penggunaan  algoritma metaheuristik Cockroach Swarm Optimization Algorithm (CSOA) sudah dilakukan oleh [7]  dalam  pencarian  solusi  sistem  persamaan  non  linier  polinomial,  campuran eksponensial  dan  trigonometri,  campuran  polinomial  dan  logaritma,  serta  campuran polinomial, eksponensial dan trigonometri. Hasil penelitian tersebut menunjukkan bahwa solusi CSOA lebih akurat daripada metode Newton-Raphson .
Beberapa  penelitian  yang  sudah  dilakukan  diatas,  fokus  pencarian  solusi  hanya  pada solusi  bilangan  riil.  Sedangkan  pada  kasus  persamaan  maupun  sistem  persamaan  yang memiliki solusi bilangan kompleks perlu untuk dilakukan kajian. Oleh karena itu, pada penelitian  ini,  algortima  metaheuristik Cockroach  Swarm  Optimization  Algorithm (CSOA) yang memiliki akurasi lebih baik dari metode Newton-Raphson akan diterapkan sebagai  pemecah  permasalahan  persamaan  non  linier  kasus  khusus  yang  memuat  akar bilangan  kompleks.  Beberapa  contoh  persamaan  non  linier  akan  diberikan  dan  akurasi yang didapatkan akan dibandingkan dengan akurasi pada metode Newton-Raphson .

## Cockroach Swarm Optimization Algorithm (CSOA)
Cockroach  Swarm  Optimization  Algorithm (CSOA)  merupakan  salah  satu Swarm Intelligent dan  algoritma  metaheuristik  yang  digunakan  pada  penelitian  ini.  Algoritma tersebut adalah suatu algoritma optimasi yang terinspirasi dari tingkah laku segerombolan kecoa dalam pencarian sumber makanan. Beberapa sifat dari kecoa yang menjadi acuan untuk penggunaan CSOA yaitu:
1. Chase-Swarming behavior (perilaku berburu)
Setiap  individu X(i) akan  memburu  (mencari) local  optimum , individual (optimum lokal individu) P(i) sesuai dengan visual scope (jangkauan pandangannya), tentu saja kebiasaan  berburu  seperti  itu  juga  menghasilkan cluster (kelompok  atau  barisan) secara simultan. Terdapat sebuah asumsi ketika sebuah individu menjadi yang terbaik dalam jangkauan pandangannya, individu itu akan mencari (mengejar) global optimum individual (optimal global individu) atau yang disebut dengan P(g) . Modelnya yaitu:
𝑋 ′ (𝑖) = { 𝑋(𝑖) + 𝑠𝑡𝑒𝑝. 𝑟𝑎𝑛𝑑. (𝑃(𝑖) − 𝑋(𝑖)), 𝑋(𝑖) ≠ 𝑃(𝑖) 𝑋(𝑖) + 𝑠𝑡𝑒𝑝. 𝑟𝑎𝑛𝑑. (𝑃(𝑔) − 𝑋(𝑖)), 𝑋(𝑖) = 𝑃(𝑖) (1)
dengan step adalah  sebuah  nilai  yang  ditetapkan  dan rand adalah  nilai  acak  antara
[0,1] .
𝑃(𝑖) = 𝑂𝑝𝑡 𝑗 { 𝑋(𝑗)   ∥ 𝑋(𝑖) − 𝑋(𝑗)| ≤ 𝑣𝑖𝑠𝑢𝑎𝑙, 𝑗 = 1,2, … , 𝑁 } (𝑖 = 1,2, … , 𝑁) (2)
𝑃𝑔 = 𝑂𝑝𝑡 𝑖 {𝑋(𝑖), 𝑖 = 1,2, … , 𝑁} (3)
dimana jarak visual diasumsikan konstan.
2. Dispersing behavior (perilaku menyebar)
Pada  interval  waktu  tertentu,  setiap  individu  menyebar  secara  acak.  Hal  ini  yang mengakibatkan perbedaan di setiap individu kecoa. Model matematikanya yaitu:
𝑋 ′ (𝑖) = 𝑋(𝑖) + 𝑟𝑎𝑛𝑑(1, 𝐷), 𝑖 = 1,2, … , 𝑁 (4)
dengan 𝑟𝑎𝑛𝑑(1, 𝐷) adalah  vektor  D-dimensional  acak  yang  dapat  diatur  dengan range tertentu.
3. Ruthless behavior (perilaku kejam)
Pada  interval  di  waktu  tertentu,  individu  terbaik  (yang  sudah  ditemukan) menggantikan individu yang dipilih secara acak, dan yang lebih kuat memangsa yang lebih lemah. Modelnya yaitu:
𝑋(𝑘) = 𝑃𝑔 (5)
dengan k adalah integer (bilangan  bulat)  acak  antara  1  sampai  banyaknya  jumlah populasi [6].

## 2. Metodologi
Pada  bagian  ini  dijelaskan  langkah-langkah  penelitian  penerapan Cockroach  Swarm Optimization  Algorithm (CSOA)  untuk  menyelesaikan  persamaan  non  linier  yang memiliki akar bilangan kompleks sebagai berikut:
Gambar 1.  Skema metode penelitian
Persamaan  non  linier  yang  digunakan  pada  penelitian  ini  yakni  berupa  persamaan polynomial,
𝑃(𝑥) = 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎 1 𝑥 + 𝑎 0 = 0 (6)
dimana 𝑥 adalah peubah dan 𝑎 𝑛 adalah konstanta [4].
Aturan  penentuan  lokasi  akar  polinom  sering  disebut  denga  aturan  tanda Descartes. Terdapat dua tahap pengerjaan yaitu tahap pertama penentuan komposisi akar polinom dengan  aturan  tanda Descartes dan  tahap  kedua  penentuan  batas  selang  akar.  Untuk menentukan komposisi akar polinom, perhatikan langkah berikut.
Misalkan, u adalah banyaknya pergantian tanda koefisien 𝑎 𝑖 dari polinom 𝑃(𝑥) dan 𝑛 𝑝 adalah banyaknya akar real positif, maka berlaku:
i. 𝑛 𝑝 ≤ 𝑢 (7)
ii. 𝑢 − 𝑛 𝑝 = 0,2,4, … (8)
Sedangkan untuk menentukan komposisi akar real negatif, misalkan v adalah banyaknya pergantian  tanda  koefisien 𝑎 𝑖 dari  polinom 𝑃(−𝑥) dan 𝑛 𝑔 adalah  banyaknya  akar  real negatif, maka berlaku:
i. 𝑛 𝑔 ≤ 𝑣 (9)
ii. 𝑣 − 𝑛 𝑔 = 0,2,4, … (10)
Studi Literatur Penyelesaian Persamaan Nonlinier Simulasi Program Cockroach Swarm Optimization Algorithm
(CSOA)
Analisis Hasil Kesimpulan

## Mengolah data dengan CSOA
Penentuan batas selang akar ditentukan oleh aturan berikut:
𝑟 = 1 + 𝑚𝑎𝑘𝑠 1≤𝑘≤𝑛 {| 𝑎 𝑘 𝑎 𝑛 |} (11)
Sehingga selang akar yang dicari adalah [−𝑟, 𝑟] .
Setelah  dilakukannya  pencarian  lokasi  akar  maka  dapat  dilakukan  proses  penyelesaian menggunakan  algoritma  CSOA.  Berikut  adalah  gambar  flowchart  dari  proses penyelesaiannya.
Gambar 2. Flowchart persamaan non linier pada CSOA

## 3. Hasil dan Pembahasan
Penerapan persamaan  non linier  pada algoritma  yang diajukan menggunakan beberapa parameter  yang  ditetapkan  sebagai  pembangkit  formula  dari  CSOA.  Parameter  yang digunakan berupa selang dugaan akar, jumlah populasi, visual, nilai dimensi vektor dan step .  Penetapan  input  serta  parameter  persamaan  di  atas  yaitu  untuk  jumlah  populasi sebanyak  50, step dan visual masing-masing  sebesar  0.5  dan  0.5.  Selang  akar  yang digunakan setiap persamaan berbeda, karena setiap persamaan dicari selang dugaan akar menggunakan aturan tanda Descartes. Peneliti menggunakan iterasi maksimum sebesar
1000 iterasi, dengan mengambil nilai random dimensi vektor [-0.01,0.01]. Pengulangan acak  dilakukan  sebanyak  10  kali  supaya  didapat  nilai fitness terbaik  dari  pengulangan tersebut. Pada percobaan penelitian digunakan 3 contoh persamaan non linier pada Tabel 1 yang memiliki akar bilangan kompleks yang diambil dari beberapa sumber yakni dari [2] dan [5] sebagai berikut.
Tabel 1.  Contoh percobaan
No Persamaan Non Linier (PNL) 1 𝑥 2 + 4𝑥 + 5 = 0 2 𝑥 3 + 2𝑥 2 + 3𝑥 + 4 = 0
3 𝑥 5 − 3𝑥 4 + 3𝑥 3 − 2𝑥 2 − 5 = 0
Tabel  2  merupakan  hasil dari penerapan CSOA.  Pada penelitian ini, penerapan  CSOA dilakukan dengan menggunakan software MATLAB .

## Tabel 2.  Hasil perhitungan CSOA menggunakan MATLAB
No
PNL
Solusi Nilai f(x) 1 -1,999997358921-1,000003437802i 8,670373234472 e -06 -1.999973190501+1.000003149304i 5.398776264334 e- 05 2 -0,174684418433-1,546881639398i 8,460206199522 e -05 -0.174652999202+1.546846296981i 2.612861888665 e -04 3 -0,548392671695+0,782421494081i 2,606296574702 e -04 -0.548385222681-0.782470713177i 1.031194591454 e -03

## 1. Pe rsamaan pertama
Parameter  yang  digunakan  sesuai  ketetapan  yang  telah  dijelaskan,  kemudian  untuk selang yang didapat dari persamaan 1 menggunakan formula persamaan (2.10) yakni antara  -5  sampai  5.  Didapat  solusi  dari  CSOA  berupa 𝑥 = −1,999997358921 − 1,000003437802𝑖 dan  nilai fitness = 8,670373234472 e -06.  Persamaan  1  yang diselesaikan menggunakan Newton-Raphson didapat solusi berupa 𝑥 = −1,999997 + 1,000008𝑖 dengan  nilai fitness =  1,708807584263𝐞 − 05 .  Pemaparan  di  atas menunjukkan  bahwa  nilai fitness yang  didapat  dari  algoritma  CSOA  lebih  baik daripada  nilai fitness dari  metode Newton-Raphson .  Nilai fitness dari  CSOA  lebih mendekati nilai nol daripada nilai fitness dari Newton-Raphson .

## 2. Persamaan kedua
Selang  akar  yang  digunakan  pada  persamaan  kedua  ini  yakni  antara  -3  sampai  3, dengan  parameter  yang  sama  didapatkan  solusi  terbaik  dari  CSOA  berupa 𝑥 = − 0,174684418433-1,546881639398 i dan nilai fitness terbaik dari 10 kali pengulangan acak yang didapat yaitu = 8,460206199522𝐞 − 05 . Solusi yang didapat dari metode Newton-Raphson dengan  penyelesaian  yang  menghasilkan 𝑥 = −0,174685 + 1,546869𝑖 dengan  nilai fitness =  1,556699603343 e -03.  Solusi  yang  tertera menunjukkan bahwasannya perbandingan nilai fitness dari CSOA dengan nilai fitness metode Newton-Raphson memiliki  perbedaan  yang  signifikan,  dimana  nilai fitness dari CSOA lebih kecil daripada Newton-Raphson. Dengan kata lain, aproksimasi dari CSOA lebih baik daripada metode Newton-Raphson.
3. Persamaan ketiga
Penyelesaian persamaan  non linier dengan CSOA dilakukan dengan terlebih dahulu mencari  selang  kisaran  akar  dengan  aturan  tanda Descartes .  Selang  akar  yang digunakan pada persamaan ketiga ini yakni antara -4 sampai 4. Dengan menggunakan parameter  yang  sama  didapatkan  solusi  terbaik  dari  CSOA  yaitu 𝑥 = −0,548392671695 + 0,782421494081𝑖 dan  nilai fitness terbaik  dari  10  kali pengulangan  acak yang  didapat  yaitu  2,606296574702 e -04.  Pendekatan  solusi  dan nilai fitness dari  metode Newton-Raphson yakni  bernilai 𝑥 = −0,552486 + 0,780503𝑖 dan fitness bernilai = 8,028366525181 e -02. Dari hasil yang didapat, maka dapat dikatakan bahwa program CSOA lebih baik dari metode Newton-Raphson untuk mendekati solusi eksak suatu persamaan polinomial dengan akar bilangan kompleks.
Prosedur Cockroach Swarm Optimization Algorithm (CSOA) Input persamaan; Input interval [a,b]; Inisialisasi parameter; Pembangkit populasi; for iter=1:iterasi maksimum for i=1:Jumlah populasi hitung nilai x’(i) pada chase-swarming behaviour hitung nilai fitness yang didapat
end
cari nilai P(g) terbaik for i=1:Populasi cari nilai Xj dari jumlah populasi; hitung nilai fitness dari Xj; for j=1:Poppulasi
cari nilai P(i) end Pengecekan terminasi End
Gambar 3. Pseudocode algoritma CSOA
Peneliti  mendapatkan  pendekatan  solusi  dari  permasalahan  persamaan  non  linier  yang memiliki  akar  bilangan  kompleks  menggunakan  CSOA  seperti  yang  telah  dipaparkan pada  Tabel  2.  Solusi  tersebut  telah  dibandingkan  dengan  metode  lain  yang  digunakan pada  beberapa  kasus  persamaan  non  linier,  yakni Newton-Raphson. Solusi-solusi  yang didapat  dari  CSOA  dan Newton-Raphson telah  dijelaskan  sepeti  diatas.  Selanjutnya, kekonvergenan output program  CSOA  divisualisasikan  dalam  bentuk  grafik kekonvergenan seperti pada Gambar 4. Grafik tersebut meunjukkan bahwa nilai fitness konvergen menuju nilai nol, yang berarti bahwa solusi yang didapatkan sudah mendekati solusi eksak.
a. PNL 1 b. PNL 2 c. PNL 3
Gambar  4.a  menunjukkan  bahwa  pada  iterasi  ke-154  nilai fitness persamaan  1  mulai konvergen  menuju  nilai  8,670373234472 e -06.  Selanjutnya  Gambar  4.b.  persamaan  2 mulai  konvergen  menuju  nilai  fitness  8,460206199522 e -05.  pada  iterasi  ke-845.  Pada Gambar  4.c.  menunjukkan  persamaan  3  konvergen  menuju  nilai fitness terbaik  yaitu 2,606296574702 e -04 pada iterasi ke-565.
Gambar 4. Konvergensi algoritma CSOA
Hasil-hasil yang didapatkan pada kasus contoh pada penelitian ini menunjukkan bahwa algoritma  CSOA  yang  diawali  dengan  pencarian  selang  menggunakan  metode  aturan tanda Descartes dapat  menjadi  alternatif  dalam  pencarian  solusi  persamaan  non  linier polinomial  yang  memiliki  akar  bilangan  kompleks.  Hasil  yang  didapatkan  juga menunjukkan bahwa solusi CSOA relatif lebih akurat dibandingkan dengan solusi yang didapatkan dengaan metode Newton-Raphson . Sedangkan untuk kasus akar bilangan riil, penerapan  algoritma  ini  relatif  lebih  mudah  diaplikasikan,  karena  tidak  memerlukan prasyarat selang akar khusus dalam pencarian solusi. Sehingga dengan nilai awal bilangan random, maka konvergensi solusi akan didapatkan.

## 4. Kesimpulan
Berdasarkan  hasil  dan  pembahasan  yang  telah  dipaparkan,  maka  bisa  disimpulkan beberapa hal sebagai berikut:
a) Cockroach  Swarm  Optimization  Algorithm (CSOA)  merupakan  salah  satu swarm intelligent yang  mampu  menyelesaikan  permasalahan  persamaan  non  linier  yang memuat  akar  kompleks  dengan  aproksimasi  yang  selalu  konvergen  pada  solusi eksak. CSOA tidak hanya bisa menemukan akar kompleks saja melainkan juga akar bilangan  riil  yang  terdapat  pada  persamaan  non  linier  yang  diujikan.  Namun  pada kasus ini, fokus kajian hanya pada akar bilangan kompleks.
b) Akurasi  dari  CSOA  dapat  dilihat  dari  perbedaan  nilai fitness yang  didapat  antara penyelesaian menggunakan CSOA dan penyelesaian menggunakan metode Newton- Raphson . Dari contoh persamaan yang diuji, CSOA memiliki nilai fitness lebih kecil dibandingkan dengan metode Newton-Raphson , hal itu menandakan bahwa CSOA memiliki keakuratan yang baik untuk penyelesaian persamaan non linier dengan akar bilangan kompleks.

## Daftar Pustaka
[1] Anwar,  Z.  (2016).  Penerapan  Gabungan  Metode  Zero  Crossing  Dan  Virus Evolutionary Genetic Algorithm (Vega) Pada Penyelesaian Persamaan Non-Linier. Skripsi .  Jember:  Fakultas  Matematika  dan  Ilmu  Pengetahuan  Alam  Universitas Jember.
[2] Ariyaratne,  M.  K.  A.,  Fernando,  T.  G.  I.,  dan  Weerakoon,  S.  (2015).  A  Modified Firefly  Algorithm  to  solve  Univariate  Nonlinear  Equations  with  Complex  Roots. Interational Conference on Advances in ICT for Emerging Regions : 160-167.
[3] Baihaki, N. A. (2016). Penerapan Algoritma Cat Swarm Optimization (CSO) Pada Penyelesaian  Sistem  Persamaan  Non-linier. Skripsi .  Jember:  Fakultas  Matematika dan Ilmu Pengetahuan Alam Universitas Jember.
[4] Basuki,  A.  dan  Ramadijanti,  N.  (2004). Metode  Numerik  Sebagai  Algoritma Komputasi . Surabaya: PENS- ITS.
[5] Muheadden, S. A. (2010). A New Technique to Compute Complex Roots. Journal of Kirkuk University-Scientific Studies . 5(2): 110-111.
[6] Obagbuwa,  I.  C.  dan  Adewumi,  A.  O.  (2014).  An  Improved  Cockroach  Swarm Optimization. The Scientific World Journal. 10(1): 1-13 .
[7] Prastowo,  F.  K.  (2016).  Penerapan  Cockroach  Swarm  Optimization  Algorithm (CSOA) Pada Penyelesaian Sistem Persamaan Non linier. Skripsi . Jember: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember.