Perdagangan Arbitrage (Algoritma Bellman-Ford)

Perdagangan di bursa biasanya dikaitkan dengan risiko. Ini benar-benar berlaku untuk sebagian besar strategi perdagangan. Keberhasilan perdagangan dalam kasus-kasus ini ditentukan semata-mata oleh kemampuan untuk dengan benar menilai risiko dan mengelolanya. Tetapi tidak semua strategi perdagangan. Ada strategi bebas risiko, yang meliputi, khususnya, arbitrase. Artikel ini akan menjelaskan apa itu arbitrase dan bagaimana mengimplementasikannya menggunakan algoritma grafik klasik seperti algoritma Bellman-Ford.

Apa itu arbitrase?

Arbitrase adalah beberapa transaksi yang berhubungan secara logis yang bertujuan untung dari selisih harga untuk aset yang sama atau terkait pada saat yang sama di pasar yang berbeda (arbitrase spasial), atau di pasar yang sama pada titik waktu yang berbeda (arbitrase sementara) .

Sebagai contoh sederhana, pertimbangkan arbitrase spasial. Di New York dan London, kesepakatan dapat dibuat untuk membeli dolar untuk euro dan euro untuk dolar. Di New York, ini dapat dilakukan pada tingkat 4 dolar untuk 3 euro, dan di London - pada tingkat 5 dolar untuk 3 euro. Perbedaan dalam tingkat ini membuka kemungkinan arbitrase spasial.



Dengan 4 dolar, di New York Anda dapat membeli 3 euro. Setelah itu, di London, beli seharga 3 euro 5 dolar ini. Seperti yang Anda lihat, urutan transaksi sederhana seperti itu menghasilkan laba 1 dolar untuk setiap 4 dolar yang diinvestasikan. Dengan demikian, jika awalnya ada $ 4 juta, maka keuntungannya akan menjadi satu juta.

Ketika nilai tukar (kami tidak mempertimbangkan spread) untuk pasangan mata uang yang sama berbeda, urutan transaksi yang diperlukan untuk menerapkan strategi arbitrase sangat sederhana. Jika nilai tukar untuk satu pasangan mata uang adalah tetap, tetapi beberapa pasangan mata uang diperdagangkan secara paralel, arbitrase juga dimungkinkan, tetapi urutan transaksi sudah tidak trivial. Misalnya, Anda dapat membeli 4 euro untuk 5 dolar, 3 pound untuk 4 euro, dan kemudian 6 dolar untuk 3 pound. Keuntungan dari urutan transaksi seperti itu adalah $ 1 untuk setiap 5 dolar yang diinvestasikan.



Ratusan pasangan mata uang dapat diperdagangkan di bursa, dan nilai tukar terus berubah. Sudah tidak mungkin untuk memahami urutan transaksi apa yang akan menghasilkan laba tanpa solusi algoritmik.

Transisi ke masalah algoritmik

Bayangkan potensi transaksi pertukaran mata uang dalam bentuk algoritmik, yaitu dalam bentuk grafik. Verteks dalam grafik ini mewakili mata uang, dan ujungnya adalah perdagangan potensial. Panjang iga sesuai dengan nilai tukar di mana transaksi dapat disimpulkan.


Pertanyaan selanjutnya adalah bagaimana menemukan urutan transaksi dalam kolom yang akan mendatangkan untung. Jelas, karena pada awal urutan dan pada akhirnya itu harus mata uang yang sama, urutannya harus sesuai dengan siklus dalam grafik yang diberikan. Selanjutnya, Anda perlu menentukan bagaimana nilai tukar antara dua mata uang dihitung, jika mereka tidak ditukar secara langsung, tetapi melalui mata uang ketiga tertentu (atau jumlah operasi perantara yang sewenang-wenang). Semuanya di sini juga cukup sederhana. Nilai tukar tersebut akan dihitung sebagai produk dari nilai tukar transaksi perantara. Urutan transaksi yang menguntungkan menjadi jika produk ini mengambil nilai kurang dari satu. Dengan kata lain, jika satu unit mata uang dapat dibeli kurang dari satu unit mata uang yang sama.


Algoritma grafik klasik tidak cocok untuk bekerja dengan produk dengan panjang tepi. Algoritma tersebut terutama diarahkan untuk menemukan jalan yang didefinisikan sebagai jumlah dari panjang ini. Namun, untuk menghindari batasan ini, ada cara matematika untuk beralih dari suatu produk ke jumlah. Cara ini adalah logaritma. Jika produk muncul di bawah logaritma, maka logaritma tersebut dapat dikonversi menjadi jumlah dari logaritma. Di sisi kanan persamaan ini, angka yang diinginkan kurang dari satu, yang berarti bahwa logaritma angka ini harus kurang dari nol.




Trik matematika sederhana semacam itu memungkinkan Anda untuk beralih dari mencari siklus yang produk panjang sisi-nya kurang dari satu ke siklus yang jumlah total panjang sisi-nya kurang dari nol. Tugas seperti itu sudah terlihat lebih dapat dipecahkan oleh algoritma grafik klasik, dan lebih tepatnya algoritma Bellman-Ford.

Bellman - Algoritma Ford

Algoritma Bellman-Ford biasanya digunakan untuk menemukan jarak dari titik yang diberikan ke semua titik lain dari grafik, tetapi modifikasinya memungkinkan menemukan siklus dengan panjang negatif.

Operasi dasar dari algoritma ini adalah relaksasi tepi. Inti dari operasi ini adalah sebagai berikut. Misalkan ada keunggulan$$$a \rightarrow b$, dan juga nilai awal jarak yang dihitung sebelumnya untuk puncak diketahui $$$a$dan $$$b$. Untuk melakukan relaksasi tepi, perlu untuk menghitung berapa jarak ke atas$$$b$jika jalan melewati puncak $$$a$dan tulang rusuk $$$a \rightarrow b$. Jarak ini dihitung sebagai jumlah jarak ke atas.$$$a$ dan panjang tulang rusuk $$$a \rightarrow b$. Lebih lanjut, jika jarak ini kurang dari jarak awal saat ini ke$$$a$maka ini adalah jarak yang sangat jauh $$$a$Sesuai dan mengambil nilai baru, baru saja dihitung,.

Algoritma lainnya juga tidak rumit. Perlu$$$N$ waktu ($$$N$Apakah jumlah simpul grafik) memotong daftar tepi, menerapkan operasi relaksasi untuk setiap putaran. Kompleksitas algoritma diperoleh$$$N*M$ (Dimana $$$N$- jumlah simpul, dan $$$M$- jumlah tulang rusuk). Untuk grafik tanpa siklus negatif, relaksasi tepi lebih lanjut tidak akan menyebabkan perubahan jarak ke simpul. Pada saat yang sama, untuk grafik yang mengandung siklus negatif, relaksasi akan mengurangi jarak ke simpul dan sesudahnya$$$N$jalan memutar. Properti ini dapat digunakan untuk menemukan siklus yang diinginkan.

Implementasi kecil berikut dari algoritma yang dijelaskan di atas pada Kotlin harus membantu mereka yang lebih terbiasa dengan memilah kode.

fun findNegativeCycle(nodes: Int, edges: Array<Edge>, source: Int): List<Int>? {
    // Initialize distances and prev arrays. All distances but the distance to
    // the source node are infinite, distance to the source node is zero.
    val distances = DoubleArray(nodes) { if (it == source) 0.0 else INFINITY }
    val prev = IntArray(nodes) { -1 }

    // Relax all edges N times where N is the number of nodes.
    repeat(nodes) {
        edges.forEach { it.relax(distances, prev) }
    }

    // Try to relax at least one more edge. If it's possible memorize the node,
    // otherwise return from the method.
    val firstRelaxedEdge = edges.firstOrNull { it.relax(distances, prev) }
    var node = firstRelaxedEdge?.to ?: return null

    // Step back N times where N is the number of nodes. As a result, the node will
    // be in the loop for sure.
    repeat(nodes) {
        node = prev[node]
    }

    // Recover the loop by the node that is inside it and prev links.
    val lastNode = node
    return buildList {
        do {
            add(node)
            node = prev[node]
        } while (node != lastNode)

        reverse()
    }
}

// Edge DTO with implemented relaxation operation.
data class Edge(val from: Int, val to: Int, val length: Double) {

    fun relax(distances: DoubleArray, prev: IntArray): Boolean {
        if (distances[from] + length >= distances[to]) {
            return false
        }

        distances[to] = distances[from] + length
        prev[to] = from
        return true
    }
}

Mari kita periksa contoh dengan grafik kecil, yang mencakup siklus panjang negatif. Agar algoritme berfungsi, setiap titik perlu mempertahankan jarak yang diketahui saat ini, serta tautan ke simpul sebelumnya. Referensi ke vertex sebelumnya dalam hal ini ditentukan oleh keberhasilan relaksasi tulang rusuk. Jika operasi relaksasi berhasil, dan jarak ke titik diperbarui, maka tautan ke titik sebelumnya dari titik ini juga diperbarui dan mengambil nilai titik sumber dari tepi yang ditentukan.

Jadi, pertama-tama Anda perlu menginisialisasi simpul dengan mengatur jarak ke semua simpul kecuali awal yang sama tanpa batas. Untuk simpul awal, jarak nol diatur.


Babak pertama dari semua tulang rusuk mengikuti dan relaksasi mereka dilakukan. Hampir semua relaksasi tidak memberikan hasil apa pun, kecuali relaksasi tulang rusuk$$$a \rightarrow b$. Relaksasi tulang rusuk ini memungkinkan Anda memperbarui jarak ke$$$b$.


Ini diikuti oleh putaran kedua dari semua tepi grafik dan relaksasi yang sesuai. Kali ini, hasilnya adalah relaksasi tulang rusuk.$$$b \rightarrow c$, dan $$$b \rightarrow d$. Jarak ke puncak diperbarui.$$$c$ dan $$$d$. Perlu dicatat di sini bahwa hasilnya tergantung pada urutan tepi yang dilintasi.


Pada rusuk ronde ketiga, adalah mungkin untuk berhasil rileks sudah tiga rusuk, yaitu rusuk $$$\rightarrow d$, $$$d \rightarrow e$, $$$d \rightarrow b$. Dalam hal ini, ketika iga santai$$$\rightarrow d$ dan $$$d \rightarrow b$sudah mencatat jarak ke $$$d$dan $$$b$, serta tautan yang sesuai ke simpul sebelumnya.


Di babak keempat, operasi rusuk berhasil diselesaikan. $$$b \rightarrow c$dan $$$b \rightarrow a$. Dalam hal ini, nilai jarak yang sudah direkam ke puncak kembali diperbarui.$$$a$ dan $$$c$, serta tautan yang sesuai ke simpul sebelumnya.


Babak kelima adalah yang terakhir. Iga santai selama jalan ini$$$\rightarrow d$, $$$d \rightarrow b$, $$$d \rightarrow e$. Di sini Anda dapat melihat bahwa keberadaan siklus panjang negatif sudah membuat penyesuaian tertentu dengan nilai jarak ke puncak.


Setelah tur ini, jika grafik tidak mengandung siklus dengan panjang negatif, algoritme akan selesai, karena relaksasi sisi mana pun tidak akan membuat perubahan apa pun. Namun, untuk grafik ini, karena adanya siklus dengan panjang negatif, orang masih dapat menemukan tepi yang relaksasi akan memperbarui jarak ke salah satu simpul.


Tepi yang relaksasi memperbarui jarak ke puncak ditemukan. Ini mengkonfirmasi adanya siklus panjang negatif. Sekarang Anda perlu menemukan siklus ini sendiri. Penting bahwa verteks, jarak yang sekarang diperbarui, dapat berada di dalam siklus dan di luarnya. Dalam contoh ini, ini adalah atas$$$e$dan dia kehabisan siklus. Selanjutnya, Anda perlu merujuk ke tautan ke simpul sebelumnya, yang diperbarui dengan hati-hati di semua langkah algoritma. Agar dijamin masuk ke dalam siklus, Anda harus melangkah mundur$$$N$puncak menggunakan tautan ini.

Dalam contoh ini, transisinya adalah sebagai berikut:$$$e \rightarrow d \rightarrow c \rightarrow b \rightarrow d \rightarrow c$. Jadi bagian atasnya berada$$$c$, yang dijamin terletak pada siklus panjang negatif.


Selanjutnya, soal teknologi. Untuk mengembalikan siklus yang diinginkan, Anda harus mengulangi lagi menggunakan tautan ke simpul sebelumnya sampai titik bertemu lagi$$$c$. Ini berarti bahwa siklus telah ditutup. Yang tersisa adalah membalik urutan, karena iterasi terbalik selama iterasi melalui tautan ke simpul sebelumnya.

Algoritma di atas mengasumsikan adanya beberapa titik awal dari mana jarak dihitung. Kehadiran vertex semacam itu tidak diperlukan agar algoritma dapat bekerja, tetapi diperkenalkan pada tingkat yang lebih besar agar sesuai dengan algoritma Bellman - Ford yang asli. Jika subjek yang menarik adalah siklus dengan panjang negatif, maka kita dapat mengasumsikan bahwa semua simpul dari grafik yang diberikan adalah awal. Dengan kata lain, bahwa jarak ke semua simpul awalnya nol.

Kesimpulan

Menggunakan algoritma Bellman-Ford dalam masalah perdagangan arbitrase adalah contoh yang sangat baik tentang bagaimana algoritma klasik dapat memecahkan masalah bisnis nyata, khususnya, di bidang keuangan. Kompleksitas asimptotik dari algoritma, sama dengan$$$N^3$untuk grafik yang terhubung penuh, grafiknya mungkin cukup besar. Ini benar-benar perlu diingat. Namun, dalam banyak kasus, seperti pertukaran mata uang, kompleksitas ini tidak menimbulkan masalah karena jumlah node yang relatif kecil dalam grafik.