2012-01-17

武田邦彦の講演会のまとめと批判

去る１月１３日に東大駒場キャンパスで武田邦彦の講演会がありました。題目は「日本で科学は可能か」

諸事情で聞きに行ったので、うろ覚えだけど（録音してないので指摘があれば該当箇所を訂正します）、話してたトピックのまとめと批判。

原発事故を防ぐのに防潮堤（防波堤）は意味をなさない
温暖化して、北極の氷が溶けても海水面に影響は与えない
- これはホントのはず。もっとも、北極海の氷が溶けても影響はないでしょうが、北極圏（グリーンランドなど）の氷が解けると、海水面に影響は出るでしょう。
ツバルの海水面上昇はヤラセだ
南極の氷は溶けていない
むしろ人間はCO2を出すべきだ
リサイクルは熱力学の法則があるのでエネルギーを無駄に使っている
大麻は禁止しなくてもいい

などなど。
順に見て行きましょうか。

2011-10-25

数式のテスト

ノート

$\array{\\{\cos(\theta)}\quad{\sin(\theta)}\\{-\sin(\theta)}\quad{\cos(\theta)}}$

2011-09-09

近似解探索戦略について（途中）

山登り法

山登り法は、最も簡単なメタヒューリスティクスである。
決定的な短所として、局所最適に捕まると脱出が不可能なので、局所最適となる解が多すぎる解空間の探索には、有効ではない。また、通常ランダムな複数の初期値から初めて、同じ最適値に収束することを確認する必要がある。

遺伝的アルゴリズム

生物の進化における、「適者生存の原理」を模した最適値探索の手法である。
（「適者生存」の原則は、ポパーがいうところの「反証可能性」がないため、実は科学ではない（科学的に検証できない）。また、生物学、生態学の最近の知見では、複数の競合する菌種を同じ培地で増殖させる実験を行ったところ、最も適応度の高い個体がすべて生きのこるという「適者生存」の原則から外れ、多くの種が生き残り、共存する結果となった。淘汰される生物がいることは事実だが、淘汰のみに注目すると、莫大な多様性を生んだ地球環境の現状に合わないという知見が見出されている。）

シミュレートされるモデルのパラメータは、０と１のバイナリーコードに変換され、これをモデルの形質を表現する遺伝子とする。
実際のパラメータを遺伝子に直すやり方は、

- 遺伝子へのコンバート方法
  - 整数を直す場合は、2進数で整数を表現
  - 刻み幅を設定した少数は、実質的に整数と同じ表現
  - 刻み幅なしで、実数を扱う場合、通常の浮動小数点の計算機内部での表現方法と同じく32bitないし64bitで表現できる。
  - 簡単なやり方では、遺伝子はただの固定長のバイナリー列。複雑な場合だと、木構造などで表現されることもある。

- 交叉
  - ニ点交叉
  - 一様交叉

- 選択
  - ルーレット選択
  - エリート選択
  - トーナメント選択

- 突然変異

交叉と、選択、突然変異の過程が現状のライブラリでは詳細が不明

どのメタヒューリスティクスを選ぶべきか（探索時間が短いか）は、問題に依存する

2011-09-03

P、NP、NP困難の概念

計算困難性の理論では、この世界の問題にはその計算の複雑さに応じて３つのクラスに分かれる。

Pクラス
NPクラス
NP困難クラス

正確にはNP完全というクラスもあるが、正確さを期すことが目的ではないので、省略する。

ここで、Pとは、多項式時間（Polylogarithmic time）の頭文字である。
（正直、Wikipediaで読んだのだが、話がややこしい上に、正しいのかどうかもよく分からん。今度、情報のTAやった先生にメールででも聞いてみよう）

あるデータサイズnの問題が与えられたとき、計算にかかる時間（もしくは計算に必要なステップ数）が、n, n log n, n^10のようなオーダーになるとき、これらを多項式時間のクラスという。

大雑把に言うと、
問題の答えを求めるのに必要な時間が多項式時間以下のものをP、
問題に解が与えられたとき、その解の真偽を判定するのに必要な時間が多項式時間以下であるものをNP
と呼ぶ。
多項式時間で答えが求まる問題であれば、解の真偽を判定するのに必要な時間は、それよりも小さいので、PはNPに含まれることは自明である。（P⊆NP）

が、PはNPの部分集合に過ぎない、つまり与えられた解の真偽は多項式時間で判定できるが、解を求めるには多項式時間で収まらないような問題が存在すると予測されている。（P≠NP予想）

例を上げると、インターネットの暗号通信の基盤となっている公開鍵暗号では、素因数分解が使われているのは有名な話だろう。これは、二つの巨大な素数の積を求めることは簡単だが、逆に二つの巨大な素数の積を、もとの素数に素因数分解することが容易ではないことを利用している。

素数をそれぞれ、p,qとしその積をNとする（N=pq）

この問題の場合、前もって素数であることが分かっているpとqから、Nを求めるのは極めて、容易である。（これはPクラスの問題）。また「p×q=N」という命題の真偽を判定するのも多項式時間内で終了する。つまりこの掛け算は、PクラスでありかつNPクラスである問題である。

ところが、Nの素因数分解は様子が違ってくる。
「Nの素因数は、pである」と言う命題の真偽を確かめるのも容易である（NPクラスの問題）。だが、「Nの二つの素因数は何か？」これは極めて難しく、有限時間で上手く解くアルゴリズムは見つかっていない。つまり、Nの素因数分解は、NPクラスではあるが、Pクラスではない。これが有名な「P≠NP予想」の内容である。

NP困難なクラスとは、NPよりもさらに難しく、与えられた解の真偽でさえ多項式時間以内に判定できない問題クラスをいう。非線形で内容が判らないような関数の最適化問題がこのクラスに該当する。「最適値を求めよ」は計算不可能、さらに「最適値はXである」と言う命題の真偽判定すら、多項式時間では終わらない。NPクラスよりもさらに困難である、という意味でNP困難と呼ばれる。

こういう問題に挑むために、近似解探索戦略（メタヒューリスティクス）が研究されている。

・山登り法
・遺伝的アルゴリズム
・タブーサーチ
・焼きなまし法
・シミュレーティッドエヴェリューション
etc...

どのメタヒューリスティクスが探索に適しているかは、問題に大きく依存する。

2011-09-02

たまには稽古日記でも

このブログ、武術の稽古会の人からリンクされてるんだが、全く書かないのも悪いので、昨日の稽古のことについてでも記述する。

昨日は抜刀と、いつもの通り杖の動きを確認、抜刀はようやくちっとは形になった気がする。あとは、歩法の稽古。

結局、自分がまっすぐに立って歩けているかどうかが最重要だという考えは変わらない。

他の術理をやってる方が楽しいけど。

2011-08-23

並列化によるシミュレーションの高速化について

半導体加工技術の進歩によって、コンピュータのCPUの性能は向上し続けている。
2005年ころまでに、それまでのクロック周波数の向上による性能向上が頭打ちとなり、CPUメーカーは一つ製品に複数のコアを搭載する、マルチコアによる性能向上が主流になった。その結果、2011年現在、一般ユーザが使うPCですら、2〜8コアのCPUを搭載するのが普通となっている。

複数個のコアが搭載されたCPUを利用する利点は、複数のアプリケーションを同時に実行しても、それらが独立に動くことにある。１つしかコアがない場合は、複数のアプリケーションを実行する際、一定時間ごとにCPUが実行するアプリケーションを切り替える（割り込み）により処理していたため、余分に時間がかかる。それに対して、マルチコアCPUの場合は、この割り込みが生じない。シミュレータでパラメータスキャンを実行する場合においても、各コアに違うパラメータを割り振ってそれぞれ独立に計算させることで、コアの数だけ計算速度が向上が期待される。

この手法を「きまりの悪い並列化」（Embarrassingly Paralllel）、あるいはタスク並列化と呼び、複数のパラメータを計算するような状況で、計算時間の短縮に極めて有効である。

並列化を実装するには、まず、以下の機能を有するスクリプトが必要となる。

スキャンするパラメータの一覧が記載されたファイルを読み込む
各パラメータから、シミュレータを起動するタスクを並列に生成する。
現在実行中のシミュレータの数を数える。

1.はプログラムの中にデータを記述しないという、構造化プログラミングの原則に則っとり、スキャンするパラメータの名称と数値を外部のファイルから与えるために必要な機能である。
2.はこのスクリプトの中核となる機能である。この機能を実装するには、「プロセスフォーク」と呼ばれるUnix系のOperating Systemの機能を利用する。プロセスフォークでは、親となるプロセスが、独立に子プロセスを生成する。この生成された子プロセスで、シミュレータをそれぞれのパラメータを計算するシミュレーションを実行するコマンドを生成・実行している。
3.は、コアの数を超えてタスクが生成された場合、割り込みによる速度低下が生じてしまうので、同時に実行するシミュレータの上限数に達した場合、他のシミュレータの実行が終了するまで、タスクの生成を待つ、という機能を実装するために必要な機能である。

このスクリプトの処理をフローチャートにすると以下の図の通りとなる。

今回、筆者が用いた計算機は、Xeonというサーバ向けブランドのCPUを2つ搭載し、物理コアを8コア、論理コアを16コア搭載するマシンである。

最大で16のシミュレータを並列で計算する能力を有しているが、OSなどの処理が割り込みに入る可能性があったり、パラメータスキャンの途中で、中止したい場合などのために、並列化されるシミュレータは15までとしている。

また、Windowsでは、Unixと同等のプロセスフォークはサポートされていないので、Perlの外部モジュールで、プロセスフォークをエミュレートさせる必要がある。さらに、Windows向けのメジャーなPerl処理系であるActivePerlでは、ひとつの親プロセスが生成することができる子プロセスの上限が64プロセスまでと制限があるため、上限に達した時点で、パラメータのリストを記述したファイルを生成し直して、スクリプトを再起動する処理を実装している。

注：下のスクリプトはファイルハンドル、ディレクトリハンドルの記法が一部、「現代的ではない」。気が向いたら書きなおす。

use strict;
use warnings;
use POSIX ":sys_wait_h";#for fork emulation

my $version = 4.0;

#main routine
#need 3 opeland parameter files.
if( @ARGV != 3 ){
    die "Parallel Simulation Scan Script:version $version \nHow to use...like...\n$0 ModelFile.ind ParameterList.csv StopTime.csv\n";# $0 is program name
}

my $model_file = $ARGV[0];#*.ind 
my $parameter_list_file=$ARGV[1];
my $stop_time_file = $ARGV[2]; chomp($stop_time_file);
my $prefix_master =$` if($model_file =~ /.ind/);
my $exe_name="fullwave.exe";
my $process_limit=15;

if (!-f $model_file || !-f $parameter_list_file || !-f $stop_time_file){
  die "No such file!\n";
}



open (my $log_file_hdl, '>', "SimulationLog.txt");
print $log_file_hdl  "Start:" . scalar localtime time() . "\n";
close ($log_file_hdl);

#Read stoptime read
my $stop_time_string;
my $time_hdl;
open $time_hdl,'<',$stop_time_file;
for (my $i=1;$i==1;$i++){
  $stop_time_string = <$time_hdl>;
  chomp($stop_time_string);
}
close($time_hdl);

open my $list_hdl,'<',$parameter_list_file;
my @lines = <$list_hdl>;
my $parameter_name_string = $lines[0];chomp($parameter_name_string);#Read Parameter Name 
close ($list_hdl);

#for (my $i=1;!eof(LIST);$i++){
my $i = 0;
foreach my $line(@lines){
  $i++;
  if ($i > 1 ){
    chomp($line);
    my $parameter_value_string = $line;
    my $generate_success=0;
    while (!$generate_success){
      if (&process_count($exe_name) < $process_limit){
        my $pid = fork;
        if (!defined $pid){
          #Rewrite parameter list 
          splice(@lines,0,$i);
          open my $list_hdl2,'>',$parameter_list_file;
          @lines = ("$parameter_name_string\n","$parameter_value_string\n",@lines);
          print $list_hdl2 @lines;
          close $list_hdl2;
          `start $0 $model_file $parameter_list_file $stop_time_file`;#cloning
          die "Original/Clone parent is dead\n";#
        }elsif($pid){ # Parent process
          print "$line stop time=$stop_time_string is simulating\n";
        }elsif(!$pid){ #Child process
          &run_simulater($parameter_name_string,$parameter_value_string,$stop_time_string);
          print "$$ exit\n";
          exit; #Kill child
        }
        $generate_success=1;
      } else {
        $generate_success=0;
        sleep 5;
      }
    }
  }
}

#terminate check
while (&process_count($exe_name) > 0){
  sleep 10;
}

open ($log_file_hdl, '>>', "SimulationLog.txt");
print $log_file_hdl  "\nStop:" . scalar localtime time() . "\n";
close ($log_file_hdl);
`shutdown -s -t 60`;

# simulation command routine (forked children)
sub run_simulater {
  (my $parameter_name_string ,my $parameter_value_string ,my $stop_time_string) = @_;
  my @parameter_name = split(/,/,$parameter_name_string);
  my @parameter_value = split(/,/,$parameter_value_string);
  my @stop_time = split(/,/,$stop_time_string);
  my $parameter_number = @parameter_name;#Number of parameters but stoptime

  foreach my $stop_time(@stop_time){
    my $prefix = $prefix_master;
    my $parameters;
    for (my $i=0 ; $i < $parameter_number ;$i++){
      $prefix .= sprintf("%s%.2f","_$parameter_name[$i]",$parameter_value[$i]);
      $parameters .= " scan_variable=$parameter_name[$i] $parameter_name[$i]=$parameter_value[$i] ";
    }
    #FDTD stop time
    $parameters .= "scan_variable=fdtd_stop_time fdtd_stop_time=$stop_time;";
    #Run command
    #print "start /min fullwave $model_file wait=0 prefix=$prefix $parameters\n";
    `start /min fullwave $model_file wait=0 prefix=$prefix $parameters`;
  }
}

#counting thread routine
sub process_count{
  (my $exe_name) = @_;
  `tasklist > process.txt`;
  open (PS, "process.txt");
  my $process_number=0;
  while (my $line = <PS>) {
    $process_number++ if ($line =~ /$exe_name/);
  }
  close (PS);
  return $process_number;
}

sub file_transaction{
  opendir(DIR,'.');
  my @files = readdir(DIR);
  closedir(DIR);
  @files = grep(/\.dat$/,@files);
  foreach my $file(@files){
    #print "$file\n";
    open(IN,$file);
    my @lines = <IN>;
    close(IN);
    open(OUT,">$file");
    foreach my $line(@lines){
      $line =~ s/^ //;
      $line =~ s/  / /g;
      $line =~ s/ $//;
      print OUT $line;
    }
    close(OUT);
  }
}

以上のようなスクリプトにより、プログラム言語に精通していないユーザでも極めて簡単、かつ高速にパラメータスキャンを行うことが可能になった。

上で述べたが、このスクリプト・プログラムは他のシミュレータでも有効である。他のシミュレータに適用するには、run_simulationという名前のサブルーチンで、シミュレータを起動するためにコマンドを生成する処理を変更すれば良いだけで、他のシミュレータへの適用は比較的容易である。

2011-08-09

Openboxを採用しているディストリ（UbuntuBased）

あんまり数はない。

CrunchBang

昔はUbuntuベースだった。
が、9.04を最後にDebianに移行。
ディストリビューターのインタビューはこちらhttp://corenominal.org/2011/05/13/crunchbang-interview-with-darth-wound。

Madbox

Ubuntuベース。バージョンは10.10。
見た目は結構かっこいい。http://www.techdrivein.com/2011/02/madbox-1010-review-ubuntu-based-openbox.html

UberBang

CrunchBangがDebianに移行したあと、有志が作った非公式CrunchBang
Madboxのレビューをしている人がやってるらしい。10.04LTS。
よさげ。http://sourceforge.jp/projects/sfnet_uberbang/