遺伝的アルゴリズムにもストーリーがあるよ、っていうはなし
遺伝的アルゴリズムとはなんなのか、をカジュアルに知りたい方へ〜遺伝的アルゴリズムの概念と、どこをどう操作していく解決方法なのかについて〜
この情報過多社会の中でそれについての情報が少ない、あるいは情報がアカデミックすぎて未熟者の私には理解困難であり卒論を書くときに困ったことがあったので、カジュアルにここにまとめました。
(Qiita記事より : 遺伝的アルゴリズムにもストーリーがあるよ、ってはなし - Qiita
)
まさに生物の遺伝だねってはなし
遺伝的アルゴリズムはとてもシンプルでナチュラル。
数学を勉強していた身からすると、わりと偶然の事象に身をまかせちゃっているから新しいなって思います。
ふつう、なんらかの問題を解くとき、あれこれ計算して最後の最後にようやくコレだ!という解が導かれます。
しかし、その計算に時間がかかる場合や、計算の仕方自体不明な場合はどうするのか。
そこで考えられたのが遺伝的アルゴリズムです。
解を進化させていくアルゴリズムを構築し、よりよい解を導くのです。
生物が何世代もの時を経て、進化してきたのと同じように。
今は、人工知能などにも応用されているそう。
より自然界に近いしくみを作ろうとしている点は同じだから、しっくりきます。
個人的には、とりあえず解を仮置きしちゃう大胆さ、そんな堅すぎないところが好きです。
だってスーパーサイヤ人的天才からしたら怠惰って思われそうだよね(?)それをこれでいいのだと貫いているのだから。
盲目コワイってはなし
遺伝的アルゴリズムを考える際に、気をつけなければならないこと。
それは、盲目にならない!ということ。
というのも、
これは絶対優秀な解だー、と思ったらそれは一時の気の迷い、あるいは勘違いで、本当の優秀な解に辿り着けなくなることがある。
解の探索はときに、からあげにレモンするのと一緒で不可逆なのです。
なので、いかに一途になりすぎず、常に広い視野を持ち、同時に選択していく勇気も持てるかがカギとなります。
そんな人になりたい…遺伝的アルゴリズムはそんな思想を持ったやつです、大人すぎる。盲目コワイ。(ちがう
要は、常によりよいものを探していけるアルゴリズムを構築せよ、ということです。
とはいえ実際にどのように進化させていくの?
いざコーディングしようとしたときに、まず何をすればいいのか分からず、なかなか自力で発想していくフェーズまで行けなかった私。
なのでここもカジュアルに文章で残しておきたいです。
ストーリーのはじまり
まずは、ランダムにつくった個体(解)の集団を0世代としてみなします。
そして、その個体が優秀なのかどうかの判断基準を適合度で表します。
これは、例えば身長が高いほうがその世界で生きていきやすいなら、長身の個体ほど適合度が大きくなるように設定します。
よりよい集団にしよッ
その世界で生きていると、優秀なものが生き残ります。
適合度が低いものは淘汰されていく、とはまさに自然界でも同じです。
淘汰って、ときに残酷に聞こえて、実はハイパー自然的現象でありこの世界には必要不可欠。
そして、このような「選択」を正しくしていけるアルゴリズムを考えるのが私たち世界支配者の仕事です。
適合度が高いほど選ばれやすいとか、適合度が1番高い個体を必ず次世代に残すとか、そんなアルゴリズムをつくりだします。
こどもが産まれたよッ
選ばれた個体同士で生殖をはじめ、子が生まれます。
その際に、遺伝子がどのように交わるか(交叉)そしてときには突然変異も起こるよね、という自然的事象をアルゴリズムに落とし込みます。
要は、こどもって親の遺伝子をどの程度受け継ぐっけ?を操作しちゃいます。
例えば、突然変異の確率をあげておくと偶発的に目新しい遺伝子をもったこどもが産まれる訳なので、盲目コワイッッを避けられるとか、そういうことが起こる訳です。
このようにして、次世代の集団をつくりだします。
よりよい世界にしよッ
これを、何度も何度でも繰り返していくことで、優秀な個体の集団になります。
きっとそれが、私たちが求めていた解、なのでしょう。
それが本当に確実に正しいのかは分かりません。
しかし、限りなく正解に近づいているはずで、そうなる可能性が高いアルゴリズムを作ることができれば、その世界の支配者として優秀ということになります。
より優秀な支配者をめざして、選択や生殖のしくみを考えるのが私たちの役目なのです。
scalaでいわゆるエコーサーバーをつくったよ
エコーサーバーとは?
ブラウザ(クライアント)から送られてきたhttpリクエストに対して、httpレスポンスでリクエストの内容をそのまま返す!それがエコーサーバーです。
(通常はここでhtmlファイルや画像を返す)
なので、ブラウザに「GET / ~~」(←リクエスト文)みたいな文字列が表示されるのがゴールです。
実装の流れは?
- 使えるjavaのパッケージをインポート(下記のリンクあり)
- サーバーソケットを生成
- while文の中にコードを書いていってサーバーソケットはacceptし続けるようにする
- 入力ストリームを作成しhttpリクエストを読み込む
- 出力ストリームを作成しhttpリクエスト文を送り返す
- ソケットを閉じる
実装コード紹介
import java.net.ServerSocket
import java.net.Socket
import java.io
import java.io.InputStream
import java.nio.charset.StandardCharsets
object HTTPServer {
def main(args: Array[String]): Unit = {
//サーバーソケットを生成しポート番号をバインドする
val serverSocket = new ServerSocket(8000)
println("Serving HTTP on localhost port 8000 ...")
while (true) {
//サーバーソケットはacceptし続けて待機
val socket = serverSocket.accept()//input--httpリクエストを読み込む
val input = socket.getInputStream
def readUntilEnd(is: InputStream, acc: List[Int] = Nil):String ={
is.read :: acc match {
case x if x.take(4) == List(10,13,10,13) => x.reverse.map(_.toChar).mkString //10,13は改行
case x => readUntilEnd(is, x)
}
}
//output--httpリクエストを送り返す
val output = socket.getOutputStream
val CRLF = "\r\n"
val responseBody = readUntilEnd(input)
val responseBodySize = responseBody.length
val responseText = "HTTP/1.1 200 OK" + CRLF +
"Content-Length: " + responseBodySize + CRLF +
"Content-Type: text/plain" + CRLF +
CRLF +
responseBody
output.write(responseText.getBytes(StandardCharsets.UTF_8))
//ソケットを閉じる
input.close()
output.close()
}
serverSocket.close()
}
}
}
基本的にやりたいことをしてくれるメソッドをここから探し出せれば完成に近づくって感じでした。 →→ Java Platform SE 8
そしてこの通信の概念というか、ソケットの存在意義、しくみを理解していればコードも読み解けます。
input 入力ストリームについて
val input = socket.getInputStream
で入力ストリームを作成すると、 情報(httpリクエスト)がトンネルを通ってどんどんやってきます。
それを一文字ずつreadして、最終的にはString型でひとつの文字列として返すreadUntilEndメソッドをつくりました。
def readUntilEnd(is: InputStream, acc: List[Int] = Nil):String ={
is.read :: acc match {
case x if x.take(4) == List(10,13,10,13) => x.reverse.map(_.toChar).mkString //10,13は改行
case x => readUntilEnd(is, x)
}
}
ここのパターンマッチではなにをしているかというと、httpリクエスト文の最後で改行がふたつ送られてきたら、再帰をやめるような条件分岐になっています。
一文字ずつByte型でリストに入ってくるので最後にすべてひっくり返して(reverse)キャラにしmkStringでリストからひとつの文字列になるようにがっちゃんこします。
output 出力ストリームについて
同じく出力ストリームを作成し、httpレスポンスの雛形に沿って情報を渡します。
ヘッダはここにあるものが全部なくても必要なものだけあれば大丈夫です。
レスポンスボディに必要なものをひとつずつ変数にString型でいれておいて、responseTextでまとめて一気にByte型に変換しソケットにwriteメソッドを適用してあげればhttpレスポンスとして送られます!
最後にソケットを閉じておわり。
かなり力づくな感じがしますがhttpサーバーってこんなことしてるんだなぁ。
すべてのものが魔法みたいに一瞬でパーンと操作されているわけじゃないことを改めて思います。笑
scalaでhttpサーバーつくり始めました
今日から実際にhttpサーバーをつくり始めました。
コードがりがりかくぞー。
まだ全然できてないですが、コンピューターとはなんぞやを知るにはhttpサーバをつくるのが一番近道なのでは?というのが所感です。
とはいえサーバーをつくるってどういうこと?ってなると思うんですが、
今日やってみて最後にやっと理解しました。
それをそうやって使うとサーバーってできるんだwwwみたいな。
今日やったこと
- サーバーソケットにホストとポートをバインドさせ接続を待ち受ける状態にする
- ローカルホストに接続してサーバーを立ち上げる
- クライアントに文字列を返してみる
と言ってもまずはhttpサーバのしくみや用語を理解していないといけないので、実質やったことで言えばインプットがほとんど。
今日理解した用語
これを理解するだけで教材が読めるようになる。
- 通信プロコトル:ネットワーク上での通信に関する規約(標準的に用いられているのTCP/IP、TCP/IP通信をソケット通信と呼ぶ)
- ソケット:プログラムの世界とTCP/IPの世界を結ぶ特別な出入り口
- ポート:何と通信するか!(IPアドレスがマンションでポート番号が部屋番号ってかんじ)
- httpパッケージ:httpリクエスト、レスポンス、URLの解析などを実装し、拡張可能なHTTPサーバと基本的なhttpクライアントを提供するもの
- ビルド:プログラムの元ネタから実際のプログラムを作る作業(コンパイルはビルドに含まれるhttp://:.com/rico/items/9ab8aa110e757a13ef37)
- カーネル:パソコンの中の執事!コンピュータ制御の中心。
- クラスSocket:クライアントソケットを実装する
- コンストラクタ:クラスからオブジェクトを作成した際に、自動的に実行されるメソッドのこと
サーバーのしくみがわかりやすかったのはこれ。
- サーバーソケットについて:http://www.techscore.com/tech/Java/JavaSE/Network/3/
サーバーってなにやってるの?
書いているコードを視覚化するとこれに尽きる。
まずはサーバーソケットを生成してaccept()で待ち状態にする。
そしてクライアント側のソケットと接続されたときにサーバーのソケットとつながる。
そこで会話をはじめます。
今回は一番簡単な文字列を返すように実装しました。
ここで、サーバーソケットを生成したり文字列(厳密にはバイト列)を送ったりするメソッドが用意されているのがjava.net。
正直これが全部頑張ってくれた。笑
コードとしてはこんなにシンプルになります!
import java.net.ServerSocket
import java.net.Socket
import java.io
object HTTPServer {
def main(args: Array[String]): Unit = {
println("Hello HTTP Server!Strat----->")
val serverSocket = new ServerSocket(8000)
println("Serving HTTP on localhost port 8000 ...")
serverSocket.accept()
//acceptし続ける
while (true) {
val socket = serverSocket.accept()println("Hello Request!")
val output = socket.getOutputStream()
output.write("HTTP/1.1 200 OK\r\n\r\nhello,cliant!".getBytes("UTF-8"))output.close()
}
}
}
writeメソッドがややこしい。
ヘッダー(HTTP/1.1 200 OK)をつけなきゃいけないし、 文字列をそのままいれられないからバイト列に変換しました!
これを、html文を送って読み取れるようにしたり、画像も送れるようになったら立派なhttpサーバーだね、ということなのですね。
サーバーをつくるってそういうことか。
ここからも楽しみ〜〜〜〜〜〜〜〜〜〜〜!
関数型がわかってきた4日目
やったこと
今日は知識系が多かったです。
今日の進歩
- 関数型を理解!!!!!!!!!!!!!!!!!!!!(おそい)
- しかもそれ数学の考え方とまったく一緒じゃん(初日にscalaは大学で生まれた言語だからそういう節あるって教えてくれてる)
- いろいろ自由自在になるよね?数学のように、と気づく
- だから型に厳しいのか、と腑に落ちる
基本構文の文法が頭に入らないなぁと思っていたら、
ひとつ下のレイヤーの言語の特徴みたいなのをちゃんと理解してなかったからだと気付きました。
あ〜〜〜〜〜〜〜〜〜〜〜〜、
ここまできたらもうなんでもできる気がするんです。
わからなかったときに、どこを調べればいいかとか、解決の仕方が見えてきた。
ここまでがつらかったよーう。
今はもっと知りたいって思う、はぁ、良かった、挫折しなくてwww
ドワンゴさんの研修資料
わかりやすかったです。
一般系を書いてくれてて、初心者が頭を整理しながら進めていくのにちょうどいいです。
https://dwango.github.io/scala_text/
ここからは自分でコードを書きながらわからないことがあったら師匠にきくという形をとっていきました。
(なんとここまでは師匠がつきっきりで見てくださっていました、だからわたしが頭が蒸発している姿とかも見られていました)
この研修資料の
- 制御構文
- クラス
- オブジェクト
をやって頭を整理し、
- 型パラメータ
- 関数
の部分を読み解きながらすすめました。
このあたりで「関数」というものに慣れてきました。
何か値を関数にいれて、なんらかの操作をし、変化した値が変数として返ってくる。
その本質を考え方の土台にすれば、問題の解き方も変わりました。
やっぱり、値を変化させたいってなると「代入」しようとしちゃうんですよね、その概念はscalaでは使えなかったんですね〜、そりゃ頭爆発するわ。
あとは、正しく値を返せるかどうかなのかな?
例えば、printlnするだけなら、
出力の型を:UNIT(何もかえってこない)にしていい感じにメソッド適用させまくればいける、みたいな感覚があるんですが。笑(まだ発言のレベルが低すぎる)
これ(出力したい値)を返すにはこのコレクションで操作できるようにしてこのメソッド適用されて、、、、って逆算していく考え方で合ってるのかな?
ここはもっと場数を踏んでいきたいな。
scala女子(仮)になれるのか、辛い、(3日目)
やったこと
- ケースクラス
- for式
- 練習問題(wordcountとか)
ようやくコードが読めるようになってきた気がします。
def メソッド名 (引数名: 引数の型) :出力の型 = {}
という形になれてきたのかな。
今思うと簡単だけど、
この形が頭に入るまではなんか難しく感じてしまって
呪文に見えたなぁ。
Optionっていうコレクションがある
あるmapの中の要素を取り出すとき、中身がなかったーーーーー!(エラー)となるのが一番よくない、ということで、あるかどうかわからないときはgetメソッドを使う。
例えば
val p = map.get("キー名")
とすると、pがオプションになる。
値があるときはsome、ないときはnoneで返ってくる。
んーなんとも不思議な概念。
これが現場ではとても役に立つのだろう。
重複をさせないケースクラス
なんか、classの前にcaseをつけると、
newいらない!valいらない!copy使える!となるそう。
インスタンス?が重複しないそう。
for式がrubyよりかなりすっきりする
for( i <- 0 to 10 ) println(n)
FizzBuzzで数字の羅列さえ表示できなかったころが懐かしい。
for { i <- 0 to 10 j <- 11 to 20 if i % 2 == 0 } println(s"$i, $j")
条件がたくさんあっても1つのforでかけちゃう。
rubyと違って全然ネストしなくてすっきり見えます。
word count問題
rubyだったらすぐかけるのに、、、(もうこれ言うのやめる)
まったくわからず撃沈しました。
これはあとで単独で記事にしよう〜!
でもわたしは思い出しました、rubyを勉強してるときも最初は自分で思いついたりしなかったことを。
どんどん正解を見て自分で書いてみて引き出しを作った方が全然早い。
これは数学を勉強してるときとすごく似てます。
例えば数学の問題が自分で解けないと「あぁわたし才能ないんだ、天才はこんなのすぐに思い付くだろうに」と思ってがーんってなるタイプでした。
だからなるべく解答は見ないし、変に頑固でした。
だけど受験生になってどれだけ効率的に点数を伸ばすかってなったら、
引き出しの数でした。
そしてそれをどれだけ多くの問題に応用できるか。
そのために一般化をするのがわたしのくせになりました。
関数的に言うと、1個しかいれてないのに100個出力される関数を目指してたみたいな。
嗚呼頭がscalaになってきたころかなぁ(ちがう)
だから、今は立ち止まらずにどんどん正解を吸収しちゃうぞ。
めざせscala女子!2日目
2日目
やったこと
- alias //iscalaというコマンドを自分で作成
- FizzBuzz問題
- Map
ツールの環境を整え、今日もテキストを進めました。
かの有名なFizzBuzz問題、rubyだったら基本構文抑えたら秒で思いつくのに。
なによりまず1-100を表示できないwwwww
なんてこった。
こんなこともできないなんてストレスフルすぎる。
rubyだったらfor i in 0..100ってするのに。
結局1to100でリストを作れることを知り、
なんとか実装。
そしてFizzBuzzの応用もいくつかあり、カンマ区切りで一列に出力するためにリストにすべて入れてからprintlnする手法などを学びました。
便利メソッドがあるのはいいけど、
知らないと思いつかないから後で
おう、、、
ってなるやつ。
あとはmapをすこし。
mapはrubyでいうhashみたいなもの。
要素はタプルっていう名前がついていて、
キーとバリューってのは同じみたい。
今日のまとめ
このレベルで頭が爆発しそうになり
帰宅後12時間爆睡しました。
なぜ爆発しそうだったかというと、おそらく、
- 基本形が分かってなくてコードが読めない、思いつかない、のループ
- たぶんコレクションもよく分かってなかった
- 型に厳しいということに慣れてなかった
- 簡単な問題なのに引き出しがないから何も思いつかなくて自分馬鹿じゃんってなって死にたってなる、のループ
そんなところでしょうか。
一貫して言えるのは、なぜわからないのかわからない、
どこの知識が抜けてるのかわからない、
というのがあったと思います。
やはり初学者はそのことについての全体像をしらない。
だからひとつひとつ単体で理解したところで、自分で自由に使えるようになるのは難しい。
わたしはもうすこし、自然的なトライアンドエラーの経験が必要ですね。
scala、はじめます
この度ただのruby初心者がscalaでHTTPサーバーを作ることになりました。
関数型ってなに…
コンパイルとか必要なかったからしたことない…
みたいなレベルから、1ヶ月間でがんばって完成させようという試みです。
スーパーエンジニアさんに教えていただきながらなので本当に心強いしありがたい。
1日目
そんなこんなで1日目。
まずは4日間scalaの基礎を勉強することに。
やったこと
- PCの環境設定
- クラス
- パターンマッチ
- コレクション
基本文法の一般系を頭にいれるよりまずさきに、クラスについて理解するために簡単なコードを読み解きました。
よくあるパーソンクラスにnameとかageとか定義してnew Personする、みたいな。
rubyでやったからわかるぞ!
まだまだここからです。