3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

1.はじめに

はじめまして、Qiita初投稿になりますkatonyonkoと申します。この記事はG's ACADEMY Advent Calendar 2022の18日目の記事です。

自己紹介

私は今年の4月まで半年間フルタイムでG's ACADEMYというエンジニアと起業家の養成スクールに通っていました。G's ACADEMYでの生活は大変充実しており、本当にかけがえのない経験を得られたと考えていますが、そんなエンジニア&起業家養成スクールを卒業した私は、その後半年ほどデータサイエンティストっぽい仕事をした後に現在は保険会社に転職して保険料計算などの仕事をしており、業務上でプログラムを書くことはあまりありません。書く場合も分析用のデータの集計のためのプログラムがほとんどなので、エンジニアとしてプログラムを書いている人にはエンジニアリング力では遠く及ばない、というかフルタイムのエンジニア&起業家養成スクールを卒業したのにエンジニアにも起業家にもなったことすらない、という客観的に見るとよくわからないキャリアを歩んでいる人です。

さらに加えて言うと、人見知りかつ出不精なためそんなに人脈も広げてこず、筆不精なため他のSNS等でも特に何も発信してこなかった私は、G's ACADEMYの中でも同期のLAB12期以外にはあまり知られていないと思います。そんな人が突然アドベントカレンダーの貴重な枠を取ってしまってごめんなさい。年末時間のあるときにたまには発信に時間を使っても良いかなと思ったのです。

2.趣味プログラミングのすすめ

ここから今回の記事の本題で、結局私はエンジニアリングとは何か、というのはよくわからないまま卒業し、今後もエンジニアリングをすることはあまりないと思うのだけど、一緒に学んできた同期やわずかに知っているエンジニアの方と話していて思うのは、プログラミングって何かを作ったり作業を効率化するための道具として捉えられていて、プログラミングすること自体が好きっていう人ってあんまりいないですよねっていう話。で、この点に関しては私は割とプログラミング自体が好きっていう自負はあって、道具として使いたいというよりむしろプログラミング自体が目的になりえるくらい楽しいものなんじゃないかなと思っている。むしろそれを使って作りたいものとか事業のアイデアとかの方は全然わいてこないというのもこんなキャリアになった理由の1つなんだけど、私からするとプログラミング自体が楽しいという気持ちが理解されないことが全然理解できない。

プログラミング楽しいよ!?

ということで、当時LAB12期生の中ではこの後で説明する競技プログラミングをずいぶん布教しようとして宣伝していたけど、結局誰も興味を持ってくれないうえ「またkatonyonkoがアルゴリズムの話始めたよ…」という冷ややかな反応を得る程度で誰にも理解してもらえなかったのでした。

そんなわけで、この記事では改めて趣味としてプログラミングすることの楽しさを伝えたい。ちなみに私は業務上でプログラムを書くことはほとんどないと言ったけど、趣味としてはほぼ毎日書いているし、やりたいことが多すぎて全然時間足りないという程度にはプログラムを書き続けている。

3.プログラミングの楽しさ

ここで改めてプログラムの何がすごいのかと考えてみると、それはやはり正確かつ高速に処理を行えるということ、つまり人間をはるかに凌駕する計算力だと思う。

これは例えばHTMLやCSSのような厳密にはプログラミング言語ではないようなものにもあてはまって、ブラウザは一瞬でこれらを正確に解釈して描画までしてくれるけど、人間がHTMLやCSSの文字列だけを読んでWebページに相当するような画像を手動で生成せよと言われたら相当きつい。というか多分私は試しもせずに諦めると思う。

また、もっと複雑なアプリを作ったり作業の自動化のためにプログラムを使うとき、コンピュータの計算能力をフルに使っていることは特に疑問の余地もないだろう。結局プログラムを書くことの強力さやメリットというのは超正確かつ高速に処理を行ってくれる(しかしちょっと融通のきかない)秘書を得られるということにあるのだと思う。

そして、そんな正確かつ高速な処理を行えるというコンピュータの能力をフルに使って、より難しい問題を解く腕を競おうというのが競技プログラミングである。逆に競技プログラミングでは、それ以外の環境構築やらデータの整形等いわゆるプログラミングで何かやろうとするときに面倒な手続きをすべて意識せずに取り組めるように設計されているため、プログラミングの根源的な楽しさのみを得ることができるのである。

こんな宣伝をLAB12では何度かやったが、結局「競技プログラミングって難しいんでしょ?オタクだけがやる趣味なのでは?」という反応だった。しかし、たとえば以下は昨日行われた競技プログラミングのコンテストAtCoder Beginner Contestの1問目だが、本当にこの問題は頭の良いごく一部の限られた人間にしか解けないものだろうか。

問題文

整数 K が与えられます。
英大文字を A から昇順に K 個繋げて得られる文字列を答えてください。

この問題は結局ABCDE…と続く26文字のアルファベットの最初のK文字を出力せよと言っているだけであり、K=3の場合は「ABC」、K=5の場合は「ABCDE」と出力することを要求しているだけである。さすがにここでは解答コードは載せないが、プログラミングをまったくやったことがない人ならともかく、プログラムを使って何かをやろうという人であれば時間はかかっても書けなければいけない程度の内容だろう。

もっと難しい問題もたくさんあって、それがだんだんオタク向けの内容になっていくことは否定しないが、このように初学者がプログラムを学ぶのに適した問題もたくさんあるのである。

特に自分がG's ACADEMYで毎週一番苦労したのはどうプログラムを書くかというところではなく、プログラムで何を作るかを考えるところであった。これは本当に難しくて、大抵のものは車輪の再発明にしかならないうえに、自分が本当に作りたいものでないとなかなか情熱をこめて作ることができない。

しかし、競技プログラミングでは何を作るかは問題が与えてくれて、あとはその要求を満たすようなプログラムを書くことだけに集中できるのである。これは自分のように本当に何が作りたいのかわかっていないような人間には大変ありがたく、作りたいものが決まっていなくてもプログラミング力の向上だけを行うことができるという利点がある(その分何を作るかを考える力が犠牲になったのかもしれないが)ため、G'sで何となくプログラミングを学ぼうと思ったけど、何を作るか決まっていない人にはぜひおすすめしたい。

4.プログラミングを用いた競技について

上記で説明したように競技プログラミングというプログラミングを用いた遊びがあるわけだが、他にもプログラミングを用いた競技というものはたくさんある。もちろん普通のハッカソンのようなものも含めれば無数にあるし、もっと競技っぽいものだけでも1人の人生では楽しみ切れないくらいあるだろう。

私は色々手を出し始めるうちに気が付いたら全然時間が足りないくらいこんなことばかりやっているのだが、自分の周りのG's生でやっている人はほとんど見なかったので、よりプログラミング力を向上する意味でもせっかく身に着けたプログラミングをもっと楽しむためにもやって損はないのではないかと思う。

もちろん合う合わないはその人の興味の方向によるのだが、競技の幅も広く多くのニーズにこたえられる世界だと思うので、むしろ興味のある分野の競技がないかという観点で調べてみると良いかもしれない。

中でも自分が今取り組んでいる&取り組みたい競技について簡単に紹介しようと思う。

競技プログラミング

上記でも紹介したAtCoderなどを含むアルゴリズムのコンテスト。日本にAtCoderがあるおかげで日本人は大変参加しやすいし、プログラミングの勉強には一番良いと思う。

AtCoder…毎週土曜日の21時から100分間のコンテストが行われる。問題の質も高く、最初の方はプログラミングの練習問題としてはうってつけ。アルゴリズムに強くなりたい人はC問題やD問題くらいまで解けるようになれば、結構色々な処理ができるようになると思う。最近はヒューリスティックコンテストもあるので、少し趣向の変わった問題も解けるようになった。

Codeforces…ロシアの競技プログラミングサイトで規模は現在世界一。コンテストの頻度が高く、AtCoderでは問題量が足りなくなった人にはちょうど良い。コンテスト時間が23:35~というパターンが多く、夜に強くない人にはきついかも。自分は翌日在宅勤務の時は結構参加して、翌日は9時ギリギリからPC起動して仕事始めることも多い。

ゲームAI

CodinGame…強いゲームAIを作るコンテスト。競技プログラミングほどはとっつきやすくないかもしれないが、ある程度プログラムを書けるようになってくると自分なりのアイデアでAIを強くできるので楽しい。ちょうどFall Challenge 2022が始まったので、この記事を書き終えたら年末年始はこれに時間を注ぎたいと思っている。

機械学習

Kaggleが一番有名かつ参加者も多いが、日本にもいくつかある。まだKaggleはあまり挑戦できていないが、今後はこちらにも時間をかけたいなと思っている。他のやつよりは実務にも役に立ちそうだし。

Kaggle…世界最大の機械学習コンペサイト。常時コンペが行われており、機械学習アルゴリズムについて学ぶにはうってつけ。当然英語サイトなので日本人には少しハードルが高くなるが、現在は機械翻訳もかなり正確なので英語できなくても十分取り組めると思う。自分も近々やりたい。

Signate…日本の機械学習コンペサイト。規模や知名度ではKaggleに劣るが、日本に関連したテーマが多くなじみやすい。取り組みやすそうなコンペでひろしまQuest2022には参加しようと思っている。そこで自分なりに満足いく結果がでたら次はKaggleかな。以前別のコンペでギリギリでメダルを取ったこともある。

その他

色々あります。あまりできてないけど、CTFとかもやっても良いかなと思ってみたり。直近で興味を持っているものだと、ksnctfは時間のあるときに少しずつ進めてみようかなという感じ。

5.進化計算コンペティションの取組

この記事の最後では、先日参加した進化計算コンペティションの取り組みについて紹介しようと思う。これは進化計算アルゴリズムを使って、より最適な解を追求するコンペである。そんなに規模は大きくなく、自分の参加した単目的部門は参加20チームだった。問題は2問出題されて、1問目は20チーム中9位、2問目は20チーム中12位と真ん中かそれよりちょっと下くらいで、特に良い成績が取れたわけでもないのだが、進化計算の勉強にもなってとても楽しかった。

コンペは頑張って上位を目指すのももちろん良い取組だが、こうやって学びたい分野の勉強としてちょっとやってみるというのも悪くない取組なのではないかと思うので、G's ACADEMYの生徒で少しでも競技に興味を持ってくれる人が出てきたら嬉しいなと思う。

問題の概要

群集シミュレーションを用いた発生交通量を推定するという問題。具体的には関門海峡花火大会終了時のメイン会場から最寄り駅までの群集移動をシミュレーションするシミュレーターがサーバー側にあって、コンペ参加者は何時何分に何人がメイン会場を出発したかという予測値のみを答える。するとサーバー側のシミュレーターが計算を行い、実際の花火大会で観測された各時刻の駅の到着人数とシミュレーターによる到着人数の差などの評価値を返してくるというもの。

コンペ参加者はこの評価値を見ながら別の解を与え、また評価値を受け取って…というプロセスを繰り返してより良い解を探していく。解の送信回数は1,000回という上限が決められているため、なるべく早く解の改善を行う戦略を考えることが必要になる。進化計算については、ここでは詳しくは説明しない(というか説明できるほどまだ理解できていない)が、このような解の探索をより高速に行うためのアルゴリズムで生物の進化過程を模して作られた手法らしい。

アルゴリズムの中身までは今回詳細に理解する時間がなかったが、実際Pythonライブラリ(optuna)の進化計算機能を使うとかなり高速に良い解にたどり着くことが確認できた。コンペでは特に良い成績は残せなかったが、今後業務上で最適化問題を解く必要がある場合には十分使える知識になったのではないかと思う。

群衆制御の重要性については、ちょうどコンペ期間(2022/10/10-2022/12/11)の途中で梨泰院の群衆事故が発生したこともあって、興味を持ちやすいテーマだったと思う。

問題への取組

ここからは時系列で取り組んだないようについて説明する。最後コロナウイルスに感染してしまったこともあり、結局消化不良で終わってしまった感は否めない。

日付 取り組んだ内容
2022/11/5,6 取組開始。本格的に取り組むにあたって、まずは問題文を読んだり解説動画を見て理解を深める。環境構築も結構大変だが、なんとかtutorialで距離関数の最小化問題をcmaで解くことはできるようになったような段階。進化計算のアルゴリズムはまだよくわかっていない。
2022/11/7-11 帰宅後ちょっと触ってみるが、tutorialで使われていたcmaを使っても途中でプログラムが異常終了する場合があることに気づく。別の進化計算ライブラリがないか調べてみたところでoptunaの中にあるCMA-ES Samplerが解説記事もあって精度も良いとのことで良さそう。ここでハイパーパラメータの最適化と同じようなことをやろうとしているという問題の構造に気づく。optunaは、ただ正規分布を入れて回しただけだが、すぐに良い性能が出て、demo1で3位くらいまで到達する。
2022/11/12,13 行動計量学会のセミナーを聞きながらdemo2のCMAESをぶん回すが、全然精度が改善しない。なぜかweight以外の変数を学習できていない(いまだに理由は不明)ようなので、500回くらい回したあとプログラムを色々いじって学習できるようになった。
2022/11/14 突然解が送信できなくなって焦る。色々試して認証が切れていただけだったことに気づく。最終的な解の送信時には気を付けなければいけないと意識する。また、過去に投げた解から途中までの学習をやり直せると良いのだが、ちょっと調べただけではやり方が見つからず、ここはいつかできるようにしておきたい。
2022/11/15 この時点でdemo1,demo2ともに3位まで到達。混合正規分布であることがわかっているうえでの本番競技と無関係な評価とはいえ嬉しい。いったんはAHCに集中するため、11/20まではお休み。そのあとやることとしては、ガウシアンフィルタを使った評価関数の再現、提出するアルゴリズムでの分布の決定(ガウシアンフィルタを使って到着者数の分布形状を見る、demoで変数いくつくらいまでならCMA-ESで十分な最適化ができるか実験、移動ガンマ分布・対数正規分布あたりが候補か)がある。まだ時間はあるが、結構やることはありそう。
2022/11/20-12/4 仕事やプライベートで遊びに行く予定が忙しくなり、ほとんど取り組めない。12/8以降で上記のやり残しを片付けることにした。
2022/12/7-10 ここで体調を崩す。PCR検査受けたら陽性だったので、やるつもりだったことがほとんど何もできなくなる。
2022/12/11 まだ体調は良くないが、せっかく途中まで取り組んだので、本番の解を送るプログラムだけ書いてあとはPCとアルゴリズムに完全にお任せすることにした。PCに一日解を送信し続けてもらって、上記のとおりsop-1で9位、sop-2で12位と真ん中くらいの成績。来年は進化計算への理解も深めてもっと良い解を出せるようにしたい。

結局使ったアルゴリズムはoptunaのCMA-ES Samplerのみで、ある程度柔軟性をもった分布を作れるようsop-1では第2種の一般化ベータ分布、sop-2ではエージェントタイプごとに対数正規分布を用いて最適化を行った。CMA-ES Samplerの性能を図りきれていなかったが、本来はもっと複雑な分布を作っても良かったのかもしれない。

また、余裕があればもっとデータの解析を行ってから解を作りたかった。

解の生成コード

最後に今回のコンペで使用した解の生成コードを貼っておく。結局CMA-ES Samplerに頼りきりなので大した工夫はないのだが、今後進化計算を実装するときの参考くらいにはなるかも。

sop1.py
import json
from subprocess import check_output
import numpy as np
from scipy.stats import norm
import optuna
from scipy import integrate
from scipy.special import beta

M=300 #300分間のシミュレーションであることを指定
N=4660 #総人数
rest=45 #各時刻の人数の最大値

def objective(trial: optuna.Trial) -> float:
  a1 = trial.suggest_uniform("a1", 0, 10)
  b1 = trial.suggest_uniform("b1", 0, 5)
  p1 = trial.suggest_uniform("p1", 0, 10)
  q1 = trial.suggest_uniform("q1", 0, 5)
  a2 = trial.suggest_uniform("a2", 0, 10)
  b2 = trial.suggest_uniform("b2", 0, 5)
  p2 = trial.suggest_uniform("p2", 0, 10)
  q2 = trial.suggest_uniform("q2", 0, 5)
  w = trial.suggest_uniform("w", 0, 10)
  b1*=40
  b2*=40
  p1/=2
  p2/=2
  def f1(t):
    if t==0: return 0
    return t**(p1-1)/((1+t)**(p1+q1))
  def f2(t):
    if t==0: return 0
    return t**(p2-1)/((1+t)**(p2+q2))
  def tr(x):
    return w/10/beta(p1,q1)*integrate.quad(f1, 0, (x/b1)**a1)[0]+(10-w)/10/beta(p2,q2)*integrate.quad(f2, 0, (x/b2)**a2)[0]
  prob = [tr(p+1)-tr(p) for p in range(M)]
  s = sum(prob)
  res = [min(rest,round(N*prob[i]/s)) for i in range(M)]
  sum_res=sum(res)
  sorted_res=sorted([(prob[i]/s,i) for i in range(M)], reverse=True)
  adjust=N-sum_res
  now=0
  while adjust>0:
    if sorted_res[now][0]<rest:
      res[sorted_res[now][1]]+=1
      adjust-=1
    now=(now+1)%M
  while adjust<0:
    res[sorted_res[now][1]]-=1
    adjust+=1
    now=(now+1)%M
  json_x = json.dumps(res)  # Convert an object into a JSON string
  json_y = check_output(  # Submit a solution and recieve the result
    ["opt", "submit", "--match=51"],
    input=json_x,  # Pass the solution via stdin
    text=True,  # Read stdout in text mode
  )
  y = json.loads(json_y)  # Convert a JSON string into a dict
  return y['objective']

if __name__ == "__main__":
  sampler = optuna.samplers.CmaEsSampler()
  study = optuna.create_study(sampler=sampler)
  study.optimize(objective, n_trials=10000)
sop2.py
import json
from subprocess import check_output
import numpy as np
from scipy.stats import norm
import optuna
import math

M=300 #300分間のシミュレーションであることを指定
N=4079 #総人数
rest=45 #各時刻の人数の最大値

def objective(trial: optuna.Trial) -> float:
  mu1 = trial.suggest_uniform("mu1", 0, 10)
  sigma1 = trial.suggest_uniform("sigma1", 0, 5)
  mu2 = trial.suggest_uniform("mu2", 0, 10)
  sigma2 = trial.suggest_uniform("sigma2", 0, 5)
  mu3 = trial.suggest_uniform("mu3", 0, 10)
  sigma3 = trial.suggest_uniform("sigma3", 0, 5)
  w1 = trial.suggest_uniform("w1", 0, 10)
  w2 = trial.suggest_uniform("w2", 0, 5)
  mu=[mu1,mu2,mu3]
  sigma=[sigma1,sigma2,sigma3]
  w=[w1/10,(1-w1/10)*w2/5,(1-w1/10)*(1-w2/5)]
  def tr(p,m,s):
    if p==0: return 0
    return norm.cdf((math.log(p)-m)/s)
  prob = [[tr(j+1,mu[i],sigma[i])-tr(j,mu[i],sigma[i]) for j in range(M)] for i in range(3)]
  s = [sum(prob[i]) for i in range(3)]
  prob = [[w[i]*prob[i][j]/s[i] for j in range(M)] for i in range(3)]
  res = [[round(N*prob[i][j]) for j in range(M)] for i in range(3)]
  sum_res=[sum([res[i][j] for i in range(3)]) for j in range(M)]
  sorted_res=sorted([(sum_res[j],j) for j in range(M)], reverse=True)
  sorted_prob=sorted([(prob[i][j],i,j) for i in range(3) for j in range(M)], reverse=True)
  for j in range(M):
    if sorted_res[j][0]>rest:
      jj=sorted_res[j][1]
      tmp=sorted([(res[i][jj],i) for i in range(3)],reverse=True)
      now=0
      for k in range(sorted_res[j][0]-rest):
        res[tmp[now][1]][jj]-=1
        now=(now+1)%3
        while res[tmp[(now+1)%3][1]][jj]<=0: now=(now+1)%3

  adjust=N-sum([sum([res[i][j] for i in range(3)]) for j in range(M)])
  now=0
  while adjust>0:
    while sum([res[i][sorted_prob[now][2]] for i in range(3)])>=rest:
      now=(now+1)%(3*M)
    d,ii,jj=sorted_prob[now]
    res[ii][jj]+=1
    adjust-=1
  while adjust<0:
    d,ii,jj=sorted_prob[now]
    res[ii][jj]-=1
    adjust+=1
    now=(now+1)%(3*M)
  json_x = json.dumps(res)  # Convert an object into a JSON string
  json_y = check_output(  # Submit a solution and recieve the result
    ["opt", "submit", "--match=52"],
    input=json_x,  # Pass the solution via stdin
    text=True,  # Read stdout in text mode
  )
  y = json.loads(json_y)  # Convert a JSON string into a dict
  return y['objective']

if __name__ == "__main__":
  sampler = optuna.samplers.CmaEsSampler()
  study = optuna.create_study(sampler=sampler)
  study.optimize(objective, n_trials=10000)

まとめ

時間を十分にかけられなかった反省もありながらも、とても楽しいコンペでした。運営の方々には感謝申し上げます。

3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?