EvbCFfp1XB

problem and my answer.

April 2017


点の座標を決める問題なので、CirclesSeparation (2013 TCO Marathon Round 3) と同じ問題だと思いました。

シミュレーテッドアニーリングしました。
最後にヒルクライミングしました。

シミュレーテッドアニーリング
  • 遷移確率は random[0,1) < exp(相対誤差/温度)
  • 温度は 0.2 -> 0 に線形に冷ます
  • 近傍の範囲も 128 -> 1 に線形に減らす


近傍

  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、前回選んだ点を中心に対称の座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 (1 + random[0,1) *
    近傍の範囲) の8方向で、スコアを最も良くする座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 {近傍の範囲*1/8, 近傍の範囲*2/8, 近傍の範囲*3/8, 近傍の範囲*4/8, 近傍の範囲*5/8, 近傍の範囲*6/8, 近傍の範囲*7/8, 近傍の範囲*8/8, } * 8方向で、スコアを最も良くする座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 (1 + random[0,1) *
    近傍の範囲) の8方向の内ランダムに移動する。
  • 前回選んだ点を、数千回に1回、最小レシオまたは最大レシオの辺の4点からランダムに1点選んで、更新する。最小レシオ,最大レシオもいっしょに更新する。
  • スコアは、最小レシオ,最大レシオを覚えておいて、選んだ点の辺のみ計算する。


ヒルクライミング

近傍

  • 改めて計算し直した、最小レシオまたは最大レシオの辺の4点からランダムに1点選んで、8近傍で最も問題のスコアが良くなる座標に移動する。

English(Google Translate)


Since it is a matter of determining the coordinates of the point, I thought it was the same problem as CirclesSeparation (2013 TCO Marathon Round 3).

I simulated annealed.
Finally I did hill climbing.

Simulated annealing

    
The transition probability is random [0, 1) <exp (relative error / temperature)
    
Cool the temperature linearly to 0.2 -> 0
    
Reduce the neighborhood range linearly to 128 -> 1


Neighborhood

    
Choose the point with the worst score at the point connected from the last point chosen, and move to the symmetrical coordinates around the last point chosen.
    
Select the point that has the worst score at the point connected from the last point chosen, and (1 + random [0, 1) *
    
Move to the coordinates that maximize the score in 8 directions of the neighborhood).
    
Select the point that has the worst score at the point connected from the last point chosen, and select {Point in the neighborhood * 1/8, the range in the vicinity * 2/8, the range in the vicinity * 3/8, the range in the vicinity * 4/8, the range of the neighborhood * 5/8, the range of the neighborhood * 6/8, the range of the neighborhood * 7/8, the range of the neighborhood * 8/8,} * Moving.
    
Select the point that has the worst score at the point connected from the last point chosen, and (1 + random [0, 1) *
    
A range in the vicinity) within the eight directions.
    
Select one point at the last time randomly from four points of the minimum ratio or the maximum ratio side once every several thousand times and update it. Update minimum ratio, maximum ratio together.
    
For the score, remember the minimum ratio, the maximum ratio, and calculate only the side of the selected point.



Hill climbing

Neighborhood

    
Randomly select one point from the four points on the minimum ratio or maximum ratio ratio that was recalculated anew and move to the coordinates with the best problem score in 8 neighborhood.



source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class GraphDrawing {
static final Watch watch = new Watch();
static final XorShift rng = new XorShift(System.nanoTime());
private SAState sa = new SAState();
private static final int size = 701;

private double score;
private double bestScore;

private Point[] points;
private Edge[] edges;
private byte[][] usedPoint = new byte[size][size];
private Point[] bestPoints;

private double[] pointIndexToScore;
private IntArray[] pointIndexToEdgeIndexes;
private int numVertices;
private int numEdges;

private static final int[] dr = new int[] { -1, -1, -1, 0, 1, 1, 1, 0, };
private static final int[] dc = new int[] { -1, 0, 1, 1, 1, 0, -1, -1, };
private int countUsed = 0;
private int countOutOfRange = 0;

public int[] plot(int numVertices, int[] edgeInformations) {
init(numVertices, edgeInformations);

solve();

int[] solution = makeSolution();

Utils.debug("time", watch.getSecond(), "score", calculateScore(), "countUsed", countUsed, "countOutOfRange", countOutOfRange);
return solution;
}

private void solve() {
points = new Point[numVertices];
for (int pointIndex = 0; pointIndex < points.length; pointIndex++) {
for (;;) {
int r = (int) (size * rng.nextDouble());
int c = (int) (size * rng.nextDouble());
assert usedPoint[r][c] >= 0;
if (usedPoint[r][c] == 0) {
points[pointIndex] = new Point(r, c);
usedPoint[r][c]++;
break;
}
}
}

bestPoints = new Point[numVertices];
for (int i = 0; i < bestPoints.length; i++) {
bestPoints[i] = new Point(0, 0);
}

pointIndexToScore = new double[numVertices];
for (int pointIndex = 0; pointIndex < points.length; pointIndex++) {
pointIndexToScore[pointIndex] = calculateLocalScore(pointIndex);
}

score = calculateScore();

SA();

greedy();
}

private void init(int numVertices, int[] edgeInformations) {
this.numVertices = numVertices;

assert edgeInformations.length % 3 == 0;
this.numEdges = edgeInformations.length / 3;

Utils.debug("numVertices", numVertices, "numEdges", numEdges);

edges = new Edge[numEdges];
for (int i = 0; i < numEdges; i++) {
edges[i] = new Edge(edgeInformations[3 * i + 0], edgeInformations[3 * i + 1], edgeInformations[3 * i + 2]);
}

pointIndexToEdgeIndexes = new IntArray[numVertices];
for (int i = 0; i < pointIndexToEdgeIndexes.length; i++) {
pointIndexToEdgeIndexes[i] = new IntArray(16);
}
for (int i = 0; i < edges.length; i++) {
pointIndexToEdgeIndexes[edges[i].pointIndex1].add(i);
pointIndexToEdgeIndexes[edges[i].pointIndex2].add(i);
}
}

private int[] makeSolution() {
int[] solution = new int[2 * numVertices];
for (int i = 0; i < numVertices; i++) {
solution[2 * i + 0] = points[i].r;
solution[2 * i + 1] = points[i].c;
}
return solution;
}

private void SA() {
double second = 1;
int mask10 = (1 << 10) - 1;
int mask14 = (1 << 14) - 1;
int mask = 1;
{
int n = 1;
while (n < edges.length) {
n <<= 1;
}
mask = n - 1;
}
for (sa.loop = 0;; sa.loop++) {

if ((sa.loop & mask10) == 0) {
if ((sa.loop & mask14) == 0) {
sa.updateTime();

if (sa.isTLE()) {
saveBest();
loadBest();
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
break;
}

sa.updateTemperature();
sa.updateRange();
}

adjustMargins();

if ((sa.loop & mask) == 0) {
pointIndexOfWorstScore();
int edgeIndex = rng.nextDouble() < 0.5 ? minRatioEdgeIndex : maxRatioEdgeIndex;
previousPointIndex = rng.nextDouble() < 0.5 ? edges[edgeIndex].pointIndex1 : edges[edgeIndex].pointIndex2;

saveBest();
}

if (sa.time > second) {
second++;
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
}
}

if (rng.nextDouble() < 0.1) {
selectAPointAndMoveToASymmetricCoordinateForOnePoint();
continue;
}
if (rng.nextDouble() < 0.1) {
selectAPointAndMoveToBestDirection();
continue;
}
if (rng.nextDouble() < 0.01) {
selectAPointAndMoveToBestDirectionAndLength();
continue;
}
selectAPointAndMoveToNearCoordinate();

}
}

private void greedy() {

sa.startTime = 9.5;
sa.endTime = 9.8;
sa.startRange = sa.endRange;
sa.startTemperature = sa.endTemperature;
sa.countChange = 0;
sa.countAccept = 0;
for (sa.loop = 0;; sa.loop++) {

sa.updateTime();

if (sa.isTLE()) {
saveBest();
loadBest();
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
break;
}

adjustMargins();

selectAPointAndMoveToBestDirectionGreedy();
}
}

private int previousPointIndex;

private void selectAPointAndMoveToBestDirection() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int length = (1 + (int) (sa.range * rng.nextDouble()));

double bestScore = -1;
int bestR = -1;
int bestC = -1;

for (int d = 0; d < dr.length; d++) {

int nextR = currentR + length * dr[d];
int nextC = currentC + length * dc[d];

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

sa.countChange++;
if (bestScore >= currentScore || sa.accept(bestScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = bestScore;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToBestDirectionGreedy() {
pointIndexOfWorstScore();
int pointIndex = (sa.loop & 1) == 0 ? (rng.nextDouble() < 0.5 ? edges[minRatioEdgeIndex].pointIndex1 : edges[minRatioEdgeIndex].pointIndex2) : (rng.nextDouble() < 0.5 ? edges[maxRatioEdgeIndex].pointIndex1 : edges[maxRatioEdgeIndex].pointIndex2);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;
double currentScore = minRatio / maxRatio;

int length = 1;

double bestScore = -1;
int bestR = -1;
int bestC = -1;

for (int d = 0; d < dr.length; d++) {

int nextR = currentR + length * dr[d];
int nextC = currentC + length * dc[d];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
continue;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateScore();

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

if (bestR == -1) {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
return;
}

sa.countChange++;
if (bestScore > currentScore) {
sa.countAccept++;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;

score = bestScore;
saveBestDoNotUpdateScore();
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToBestDirectionAndLength() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int bestR = -1;
int bestC = -1;

double bestScore = -1;
int bestDirection = -1;
for (int d = 0; d < dr.length; d++) {

int nextR = currentR + dr[d];
int nextC = currentC + dc[d];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
continue;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
bestDirection = d;
}
}

if (bestDirection == -1) {
return;
}

int deltaLength = (int) (Math.ceil(sa.range / 8.0));
for (int i = 0; i < 8; i++) {

int length = i * deltaLength;
int nextR = currentR + length * dr[bestDirection];
int nextC = currentC + length * dc[bestDirection];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
break;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

sa.countChange++;
if (bestScore >= currentScore || sa.accept(bestScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = bestScore;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToNearCoordinate() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int direction = (int) (dr.length * rng.nextDouble());
int length = (1 + (int) (sa.range * rng.nextDouble()));
int nextR = currentR + length * dr[direction];
int nextC = currentC + length * dc[direction];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
direction = (direction + (dr.length >>> 1)) % dr.length;
nextR = currentR + length * dr[direction];
nextC = currentC + length * dc[direction];
}

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
return;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

sa.countChange++;
if (nextScore >= currentScore || sa.accept(nextScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = nextScore;
usedPoint[currentR][currentC]--;
usedPoint[nextR][nextC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}

}

private void selectAPointAndMoveToASymmetricCoordinateForOnePoint() {
int edgeIndex = edgeIndexOfLocalWorstScore(previousPointIndex);
int pointIndex = edges[edgeIndex].pointIndex1 == previousPointIndex ? edges[edgeIndex].pointIndex2 : edges[edgeIndex].pointIndex1;
int pointIndex2 = edges[edgeIndex].pointIndex1 == previousPointIndex ? edges[edgeIndex].pointIndex1 : edges[edgeIndex].pointIndex2;
assert pointIndex2 == previousPointIndex;
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int nextR = points[pointIndex].r + 2 * (points[pointIndex2].r - points[pointIndex].r);
int nextC = points[pointIndex].c + 2 * (points[pointIndex2].c - points[pointIndex].c);

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
return;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

sa.countChange++;
if (nextScore >= currentScore || sa.accept(nextScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = nextScore;
usedPoint[currentR][currentC]--;
usedPoint[nextR][nextC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}

}

private double calculateScore() {
double min = 1e99;
double max = -1e99;
for (int i = 0; i < edges.length; i++) {
double ratio = calculateSquaredDistance(edges[i]) * edges[i].inverseSquaredDesiredLength;
min = Math.min(min, ratio);
max = Math.max(max, ratio);
}
return Math.sqrt(min / max);
}

private double minRatio;
private double maxRatio;
private int minRatioEdgeIndex;
private int maxRatioEdgeIndex;

private void pointIndexOfWorstScore() {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < edges.length; i++) {
double ratio = calculateSquaredDistance(edges[i]) * edges[i].inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = i;
}
if (ratio > max) {
max = ratio;
maxi = i;
}
}
minRatio = Math.sqrt(min);
maxRatio = Math.sqrt(max);
minRatioEdgeIndex = mini;
maxRatioEdgeIndex = maxi;
}

private double calculateLocalScore(int pointIndex) {
double min = 1e99;
double max = -1e99;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
Edge edge = edges[pointIndexToEdgeIndexes[pointIndex].values[i]];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
min = Math.min(min, ratio);
max = Math.max(max, ratio);
}
return Math.min(Math.sqrt(min) / maxRatio, minRatio / Math.sqrt(max));
}

private int pointIndexOfLocalWorstScore(int pointIndex) {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
int edgeIndex = pointIndexToEdgeIndexes[pointIndex].values[i];
Edge edge = edges[edgeIndex];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = edgeIndex;
}
if (ratio > max) {
max = ratio;
maxi = edgeIndex;
}
}
return (Math.sqrt(min) / maxRatio < minRatio / Math.sqrt(max) ? (edges[mini].pointIndex1 == pointIndex ? edges[mini].pointIndex2 : edges[mini].pointIndex1) : (edges[maxi].pointIndex1 == pointIndex ? edges[maxi].pointIndex2 : edges[maxi].pointIndex1));
}

private int edgeIndexOfLocalWorstScore(int pointIndex) {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
int edgeIndex = pointIndexToEdgeIndexes[pointIndex].values[i];
Edge edge = edges[edgeIndex];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = edgeIndex;
}
if (ratio > max) {
max = ratio;
maxi = edgeIndex;
}
}
return (Math.sqrt(min) / maxRatio < minRatio / Math.sqrt(max) ? mini : maxi);
}

private double calculateSquaredDistance(Edge edge) {
int dr = points[edge.pointIndex1].r - points[edge.pointIndex2].r;
int dc = points[edge.pointIndex1].c - points[edge.pointIndex2].c;
return (dr * dr + dc * dc);
}

private void loadBest() {
score = bestScore;
for (int i = 0; i < points.length; i++) {
points[i].r = bestPoints[i].r;
points[i].c = bestPoints[i].c;
}
}

private void saveBest() {
score = calculateScore();
if (score > bestScore) {
bestScore = score;
for (int i = 0; i < points.length; i++) {
bestPoints[i].r = points[i].r;
bestPoints[i].c = points[i].c;
}
}
}

private void saveBestDoNotUpdateScore() {
if (score > bestScore) {
bestScore = score;
for (int i = 0; i < points.length; i++) {
bestPoints[i].r = points[i].r;
bestPoints[i].c = points[i].c;
}
}
}

private void adjustMargins() {
int minR = (int) 1e9;
int maxR = (int) -1e9;
int minC = (int) 1e9;
int maxC = (int) -1e9;
for (int i = 0; i < points.length; i++) {
minR = Math.min(minR, points[i].r);
maxR = Math.max(maxR, points[i].r);
minC = Math.min(minC, points[i].c);
maxC = Math.max(maxC, points[i].c);
}

int marginL = minC - 0;
int marginR = 700 - maxC;
int marginD = minR - 0;
int marginU = 700 - maxR;

int newMarginD = (marginD + marginU) / 2;
int deltaR = newMarginD - marginD;
int newMarginL = (marginL + marginR) / 2;
int deltaC = newMarginL - marginL;

for (int i = 0; i < points.length; i++) {
usedPoint[points[i].r][points[i].c]--;
points[i].r += deltaR;
points[i].c += deltaC;
usedPoint[points[i].r][points[i].c]++;
}

}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

int N = Integer.parseInt(br.readLine());
int E = Integer.parseInt(br.readLine());
int[] edges = new int[E];
for (int i = 0; i < E; ++i) {
edges[i] = Integer.parseInt(br.readLine());
}

GraphDrawing gd = new GraphDrawing();
int[] ret = gd.plot(N, edges);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Point {
int r;
int c;

public Point(int r, int c) {
this.r = r;
this.c = c;
}
}

class Edge {
int pointIndex1;
int pointIndex2;
double inverseSquaredDesiredLength;

public Edge(int pointIndex1, int pointIndex2, int desiredLength) {
super();
this.pointIndex1 = pointIndex1;
this.pointIndex2 = pointIndex2;
this.inverseSquaredDesiredLength = 1.0 / (desiredLength * desiredLength);
}

@Override
public String toString() {
return "[" + pointIndex1 + "," + pointIndex2 + "]";
}

}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 9.5;
public double time = startTime;

public double startTemperature = 2 * 1e-1;
public double endTemperature = 0;
public double temperature = startTemperature;

public double startRange = 128;
public double endRange = 1;
public double range = startRange;

public int loop;
public int countChange;
public int countAccept;

public void updateTemperature() {
temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateRange() {
range = (endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0));
}

public void updateTime() {
time = useTime ? GraphDrawing.watch.getSecond() : loop;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore < 0;
assert temperature >= 0;
return GraphDrawing.rng.nextDouble() < StrictMath.exp((newScore - currentScore) / (currentScore * temperature));
}
}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

class Watch {
private long start;

public Watch() {
init();
}

public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}

public void init() {
init(System.nanoTime());
}

private void init(long start) {
this.start = start;
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

class IntArray {
public int[] values;
public int length;

public IntArray() {
this(new int[4], 0);
}

public IntArray(int capacity) {
this(new int[capacity], 0);
}

public IntArray(int[] values) {
this(values, values.length);
}

public IntArray(int[] values, int length) {
this.values = values;
this.length = length;
}

public void add(int value) {
if (length == values.length) {
values = Arrays.copyOf(values, values.length << 1);
}
values[length++] = value;
}

public int remove() {
return values[--length];
}

public boolean contains(int value) {
for (int i = 0; i < length; i++) {
if (values[i] == value) {
return true;
}
}
return false;
}

public void clear() {
length = 0;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < length; i++) {
sb.append(values[i] + ",");
}
sb.append("}");
return sb.toString();
}

public boolean isEmpty() {
return length == 0;
}

public int remove(int index) {
if (index >= length) {
throw new AssertionError();
}

if (index == length - 1) {
return remove();
}

int res = values[index];
System.arraycopy(values, index + 1, values, index, length - (index + 1));
length--;

return res;
}

public void set(int index, int value) {
if (index >= length) {
throw new AssertionError();
}

if (length >= values.length - 1) {
values = Arrays.copyOf(values, values.length << 1);
}
System.arraycopy(values, index, values, index + 1, length - index);
length++;

values[index] = value;
}

public IntArray copy() {
return new IntArray(Arrays.copyOf(values, length), length);
}

public int[] toArray() {
return Arrays.copyOf(values, length);
}

}








ネットワークの構成を変えると、結果がどのように変わるか実験してみました。

FacialEmotions seed1

System test 1位(Psyho)と2位(wleite)




sse
Psyho


82.6467632504
wleite


80.3573356044



d = dropout
c = convolutional layer
b = batch normalization
r = rectified linear unit (ReLU)
m = max pooling
l = Linear layer (a.k.a. fully-connected layer)
s = softmax

convolutional layer を 3 回使います。
net epoch loss accuracy sse
crmcrmcrmlrls 10 0.862057242 0.6888581587 84.8293236042
crmcrmcrmlrls 20 0.2330729473 0.9241406559 110.2754166642


Batch Normalizationを使いました。
net epoch loss accuracy sse
cbrm cbrm cbrm lbr ls 10 0.0292957636 1 98.5088547936
 
Batch Normalization を使う位置を変えました。
net epoch loss accuracy sse
crbmcrbmcrbmlrbls 10 0.0161193058 1 103.3351983911
crmbcrmbcrmblbrls 10 0.0428612025 0.9990122481 104.5428854816

dropout を使いました。
net epoch loss accuracy sse
d cbrm cbrm cbrm lbr ls 10 0.6779491677 0.7741999208 127.6396549389
cdbrm cbrm cbrm lbr ls 10 0.1860714287 0.9697747926 97.3982535937
cbdrm cbrm cbrm lbr ls 10 0.1261851785 0.9891347294 90.293485705
cbrdm cbrm cbrm lbr ls 10 0.1165383348 0.9877518768 135.9137072744
cbrm d cbrm cbrm lbr ls 10 0.3982799557 0.8860134335 89.3255575127
cbrm cdbrm cbrm lbr ls 10 0.3108963729 0.9205847492 87.1665944558
cbrm cbdrm cbrm lbr ls 10 0.2976720617 0.9265112604 87.8945815325
cbrm cbrdm cbrm lbr ls 10 0.2908983695 0.9274990119 97.0035103791
cbrm cbrm d cbrm lbr ls 10 0.6466208026 0.7740023707 82.3041648362
cbrm cbrm d cbrm lbr ls 10 0.6593907256 0.7710391151 87.7033221745
cbrm cbrm cdbrm lbr ls 10 0.5000952218 0.8356380879 85.98265144
cbrm cbrm cbdrm lbr ls 10 0.4267725744 0.8735677599 83.6281797147
cbrm cbrm cbrdm lbr ls 10 0.4398758164 0.8619122878 87.4801027678
cbrm cbrm cbrm d lbr ls 10 0.7070338922 0.7443698141 85.7758809568
cbrm cbrm cbrm d lbr ls 10 0.7025089265 0.7459502175 83.1445387195
cbrm cbrm cbrm ldbr ls 10 0.6557939961 0.7773607272 98.114469585
cbrm cbrm cbrm lbdr ls 10 0.44960894 0.8561833265 105.3589899718
cbrm cbrm cbrm lbr d ls 10 0.4411115036 0.8555906757 84.4414017709
cbrm cbrm cbrm lbr l b s 10 0.350525047 0.9998024496 107.6956465493

dropout を2回以上使いました。

net epoch loss accuracy sse
cbrmDcbrmcbrmlbrDls 20 0.4687651145 0.8354405375 88.8934547861
cbrmDcbrmcbrmDlbrls 20 0.646407447 0.7635322005 83.6677099091
cbrmDcbrmDcbrmlbrls 20 0.4206087752 0.8668510471 88.9427621938
cbrmcbrmDcbrmlbrDls 20 0.697579882 0.7500987754 81.9197008873
cbrmcbrmDcbrmDlbrls 20 0.7615070114 0.7354800472 78.8430071664
cbrmcbrmcbrmDlbrDls 20 0.7329212929 0.7412090082 83.007588472
cbrmDcbrmDcbrmDlbrls 20 0.8634045921 0.6959699726 79.3253190373
cbrmDcbrmDcbrmlbrDls 20 0.8133866381 0.7044646383 79.0648046938
cbrmDcbrmcbrmDlbrDls 20 0.9094222649 0.6716712761 80.0929658934
cbrmcbrmDcbrmDlbrDls 20 0.9502801996 0.66851047 78.9084275277
cbrmDcbrmDcbrmDlbrDls 20 1.037415473 0.6309758988 79.860401207





source code (cbrmDcbrmDcbrmDlbrDls)


#coding: utf-8
import numpy as np
import sys
import chainer
from chainer import cuda
import chainer.functions as F
import chainer.links as L
from chainer import optimizers
import time
import pickle
import os.path


class Net(chainer.Chain):

def __init__(self, class_labels=7):
super(Net, self).__init__(
conv1=L.Convolution2D( 3, 64, 3, stride=1, pad=1),
bn1=L.BatchNormalization(64),
conv2=L.Convolution2D( 64, 64, 3, stride=1, pad=1),
bn2=L.BatchNormalization(64),
conv3=L.Convolution2D( 64, 64, 3, stride=1, pad=1),
bn3=L.BatchNormalization(64),

fc1=L.Linear(None, 64, nobias=True),
bn_fc1=L.BatchNormalization(64),
fc2=L.Linear(None, class_labels, nobias=True),
bn_fc2=L.BatchNormalization(class_labels)
)

def __call__(self, x, y, train=True):
h = self.conv1(x)
h = self.bn1(h, test=not train)
h = F.relu(h)
h = F.max_pooling_2d(h, ksize=2, stride=2)

h = F.dropout(h, ratio=0.5, train=train)

h = self.conv2(h)
h = self.bn2(h, test=not train)
h = F.relu(h)
h = F.max_pooling_2d(h, ksize=2, stride=2)

h = F.dropout(h, ratio=0.5, train=train)

h = self.conv3(h)
h = self.bn3(h, test=not train)
h = F.relu(h)
h = F.max_pooling_2d(h, ksize=2, stride=2)

h = F.dropout(h, ratio=0.5, train=train)

h = self.fc1(h)
h = self.bn_fc1(h, test=not train)
h = F.relu(h)

h = F.dropout(h, ratio=0.5, train=train)

h = self.fc2(h)
# h = self.bn_fc2(h, test=not train)
# h = F.relu(h)
# h = F.dropout(h, ratio=0.5, train=train)

if train:
return F.softmax_cross_entropy(h, y), F.accuracy(h, y)
else:
return F.softmax(h)

class FacialEmotions:
def __init__(self):
self.startTime = time.perf_counter();

# self.useModel = True
self.useModel = False

# self.train_size10 = True
self.train_size10 = False

self.train = []
self.train_result = []
self.train_index = 0
self.test = []
self.test_index = 0


self.batchsize = 128
self.useSmallImage = True
# self.useSmallImage = False
self.size = 64
self.model = Net()

self.folder = "./python/cbrmDcbrmDcbrmDlbrDls/"

# pkl_file = open(self.folder + "FacialEmotions.pkl", "rb")
# self.model = pickle.load(pkl_file)
# print("load model", file=sys.stderr)
# sys.stderr.flush()

def newImage(self, img):
three = self.oneDimensionToThreeDimension(img)

if self.useSmallImage == True:
three = self.smallImage(three)

return self.cropImage(three, (len(three[0])//2) - (self.size//2), (len(three[0][0])//2) - (self.size//2), self.size, self.size)

def cropImage(self, img, startR, startC, sizeR, sizeC):
crop = np.zeros((3, sizeR, sizeC))
for color in range(3):
for r in range(sizeR):
for c in range(sizeC):
crop[color][r][c] = img[color][startR + r][startC + c]
return crop

def smallImage(self, img):
sizeR = len(img[0])//2
sizeC = len(img[0][0])//2
# print("sizeR : {}, sizeC : {}\n".format(sizeR , sizeC), file=sys.stderr)
# sys.stderr.flush()
small = np.zeros((3, sizeR, sizeC))
for color in range(3):
for r in range(sizeR):
for c in range(sizeC):
small[color][r][c] = img[color][2 * r + 0][2 * c + 0]
small[color][r][c] += img[color][2 * r + 0][2 * c + 1]
small[color][r][c] += img[color][2 * r + 1][2 * c + 0]
small[color][r][c] += img[color][2 * r + 1][2 * c + 1]
small[color][r][c] /= 4
return small

def oneDimensionToThreeDimension(self, img):
three = np.zeros((3, 250, 250))
for r in range(250):
for c in range(250):
value = img[r * 250 + c]
red = (value >> 16) & 255
green = (value >> 8) & 255
blue = (value >> 0) & 255
three[0][r][c] = red
three[1][r][c] = green
three[2][r][c] = blue
return three

def flipImage(self, img):
sizeR = len(img[0])
sizeC = len(img[0][0])
flip = np.zeros((3, sizeR, sizeC))
for color in range(3):
for r in range(sizeR):
for c in range(sizeC):
flip[color][r][c] = img[color][r][(sizeC - 1) - c]
return flip

def training(self, img, emot):
if self.useModel == True:
return 1

elif os.path.isfile("./python/training_seed1.pkl"):
pkl_file = open("./python/training_seed1.pkl", "rb")
self.train = pickle.load(pkl_file)
pkl_file = open("./python/training_result_seed1.pkl", "rb")
self.train_result = pickle.load(pkl_file)
print("load training data", file=sys.stderr)
sys.stderr.flush()
return 1

if self.train_index % 100 == 0:
print(self.train_index, file=sys.stderr)

image = self.newImage(img)
self.train.append(image)
# self.train.append(self.flipImage(image))

emotion = 0
for i in range(7):
emotion += (i+0) * emot[i]
self.train_result.append(emotion)
# self.train_result.append(emotion)

self.train_index+=1

if self.train_size10 == True and self.train_index == 10:
return 1

return 0

def training2(self):
if os.path.isfile("./python/training_seed1.pkl") == False:
pickle.dump(self.train, open("./python/training_seed1.pkl", "wb"), -1)
pickle.dump(self.train_result, open("./python/training_result_seed1.pkl", "wb"), -1)
print("save training data", file=sys.stderr)
sys.stderr.flush()

self.train = np.array(self.train, dtype=np.float32)
self.train_result = np.array(self.train_result, dtype=np.int32)

self.train /= 255.0

optimizer = optimizers.Adam()
optimizer.setup(self.model)

batchsize = self.batchsize
n_epoch = 20

x_train = self.train
y_train = self.train_result
N = len(y_train)

elapse = int(time.perf_counter() - self.startTime)
print("start, time: {}:{}:{}".format(elapse//(60*60), (elapse%(60*60))//(60), elapse%60), file=sys.stderr)
sys.stderr.flush()
for epoch in range(1, n_epoch + 1):

perm = np.random.permutation(N)
sum_loss = 0
sum_accuracy = 0
for i in range(0, N, batchsize):
x_batch = np.asarray(x_train[perm[i:i + batchsize]])
y_batch = np.asarray(y_train[perm[i:i + batchsize]])

optimizer.zero_grads()
loss, accuracy = self.model(x_batch, y_batch, train=True)
loss.backward()
optimizer.update()
sum_loss += float(loss.data) * len(y_batch)
sum_accuracy += float(accuracy.data) * len(y_batch)

pickle.dump(self.model.to_cpu(), open(self.folder + "FacialEmotions" + str(epoch) + ".pkl", "wb"), -1)
print("save model", file=sys.stderr)
sys.stderr.flush()

elapse = int(time.perf_counter() - self.startTime)
print("epoch: {}, time: {}:{}:{}, loss: {}, accuracy: {}".format(epoch, elapse//(60*60), (elapse%(60*60))//(60), elapse%60, sum_loss / N, sum_accuracy / N), file=sys.stderr)
sys.stderr.flush()

pickle.dump(self.model.to_cpu(), open(self.folder + "FacialEmotions.pkl", "wb"), -1)
print("save model", file=sys.stderr)
sys.stderr.flush()


def testing(self, img,*args):
if self.test_index % 10 == 0:
print(self.test_index, file=sys.stderr)
sys.stderr.flush()

if self.useModel == True and self.test_index == 0:
pkl_file = open(self.folder + "FacialEmotions.pkl", "rb")
self.model = pickle.load(pkl_file)
print("load model", file=sys.stderr)
sys.stderr.flush()

elif self.test_index == 0:
self.training2()

self.test_index += 1

newImg = self.newImage(img)

test = []
test.append(newImg)
test = np.array(test, dtype=np.float32)
test /= 255.0

prediction = self.model(test, None, train=False)

return prediction.data[0]

if __name__ == "__main__":

fe = FacialEmotions()
N = int(input())
for i in range(N):
S = int(input())
imageData = []
for j in range(S):
imageData.append(int(input()))
emotions = []
for j in range(7):
emotions.append(float(input()))
ret = fe.training(imageData, emotions)
print(ret)
sys.stdout.flush()
if ret == 1:
break

M = int(input())
for i in range(M):
S = int(input())
imageData = []
for j in range(S):
imageData.append(int(input()))
emotions = fe.testing(imageData)
for emotion in emotions:
print(emotion)
sys.stdout.flush()






このページのトップヘ